昨天在面试中，我被问到以下问题：
考虑一个Java或C++数组，例如X，其中元素已排序且没有两个元素相同。如何最好地找到一个索引i，使该索引处的元素也等于i。也就是说，X [i] = i。
为了澄清，她还给了我一个示例：
Array X : -3 -1 0 3 5 7
index : 0 1 2 3 4 5
Answer is 3 as X[3] = 3.
我能想到的最好方法是线性搜索。面试后，我对这个问题思考了很多，但没有找到更好的解决方案。我的论点是：具有所需属性的元素可以在数组的任何位置。因此，它也可能在数组的末尾，因此我们需要检查每个元素。
我只是想从社区这里确认一下我是正确的。请告诉我我是正确的 :)
通过略微修改的二分查找算法，可以在O(logN)时间和O(1)空间内完成。
考虑一个新数组Y，使得 Y[i] = X[i] - i。
Array X : -3 -1 0 3 5 7
index : 0 1 2 3 4 5
Array Y : -3 -2 -2 0 1 2
由于X中的元素是按 递增排序的，所以新数组Y中的元素将是非降序的。因此，在Y中进行0的二分查找将得到答案。
但创建Y将需要O(N)的空间和O(N)的时间。因此，您可以修改二分查找算法，使Y[i]的引用替换为X[i] - i。
算法：
function (array X)
low = 0
high = (num of elements in X) - 1
while(low <= high)
mid = (low + high) / 2
// change X[mid] to X[mid] - mid
if(X[mid] - mid == 0)
return mid
// change here too
else if(X[mid] - mid < 0)
low = mid + 1;
else
high = mid - 1;
end while
return -1 // no such index exists...return an invalid index.
end function
equals(Integer that) { return that - X.indexOf(that) == 0; } 或者一个compareTo方法，例如 compareTo(Integer other) { return other - axList.indexOf(other); } 我刚试了一下，由于类型安全原因，Java不允许我这样做。 - GlenPetersonarr[5] = 4，则arr[4] <= (4 - 1)，arr[3] <= (4 - 2)等等。如果中间元素大于其索引，则可以应用类似的逻辑。Java实现：int function(int[] arr) {
int low = 0;
int high = arr.length - 1;
while(low <= high) {
int mid = high - (high - low) / 2;
if(arr[mid] == mid) {
return mid;
} else if(arr[mid] < mid) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // There is no such index
}
arr[5] = 3，那么解决方案可能仍然在 arr[4] 中或者在 arr[6] 中。我认为我们无法在上述代码中选择一个方向。 - dchhetriarr已经排序，因此arr[4]必须小于3，因此我们必须从索引6开始寻找解决方案。 - Vasux[i] 是严格递增的，那么 x[i]-i 就是非递减的。 - Steve Jessopi 使得 x[i] == 300”，而是“如何找到一个索引 i 使得 x[i] == i”。如果没有考虑到这一点，我不认为这个答案是正确的（尽管它肯定是对插值搜索的良好描述）。 - Steve Jessop//invariant: startIndex <= i <= endIndex
int modifiedBsearch(int startIndex, int endIndex)
{
int sameValueIndex = -1;
int middleIndex = (startIndex + endIndex) /2;
int middleValue = array[middleIndex];
int endValue = array[endIndex];
int startValue = array[startIndex];
if(middleIndex == middleValue)
return middleValue;
else {
if(middleValue <= endIndex)
sameValueIndex = modifiedBsearch(middleIndex + 1, endIndex)
if(sameValueIndex == -1 && startValue <= middleIndex)
sameValueIndex = modifiedBsearch(startIndex, middleIndex -1);
}
return sameValueIndex;
}
我想修改二分查找的版本就可以了。
假设这个序列是
Array : -1 1 4 5 6
Index : 0 1 2 3 4
Result : 1
或者
Array : -2 0 1 2 4 6 10
Index : 0 1 2 3 4 5 6
Result: 4
从这两个例子中我们可以看出，如果mid < a[mid]，那么所需的结果永远不会在右侧... 伪代码大致如下
mid <- (first + last )/2
if a[mid] == mid then
return mid
else if a[mid] < mid then
recursive call (a,mid+1,last)
else
recursive call (a,first,mid-1)
int ABC[] = { -2, -5, 4, 7, 11, 22, 55 };
void main()
{
int X[] = { -3, -1, 0, 3, 5, 7};
int length = sizeof(X)/sizeof(X[0]);
for (int i = 0; i < length;) {
if (X[i] > i && X[i] < length)
i = X[i]; // Jump forward!
else if (X[i] == i) {
printf("found it %i", i);
break;
} else
++i;
}
}
就我个人而言，使用二分法可能会更快。
查看中间值，如果它比所需值高，则在较低的一半重新搜索。
经过一次比较，您已经将数据集一分为二。
Java：
public static boolean check (int [] array, int i)
{
if (i < 0 || i >= array.length)
return false;
return (array[i] == i);
}
C++：
bool check (int array[], int array_size, int i)
{
if (i < 0 || i >= array_size)
return false;
return (array[i] == i);
}
x[i]=3的位置。这个问题很有趣。如果候选人能立即回答，很可能他们以前见过这道题，但他们也可能很聪明，在一开始就发现了额外的技巧。如果候选人在30秒后才回答，说明他们发现了这个技巧。如果他们无法回答，说明他们没有发现。为了区分聪明和有知识的人，请用一个float类型的数组来询问，看看是否得到相同的（现在是错误的）答案;-) - Steve Jessop