思路
这道题的输入是一个等差数列,当然其中缺失了一项。
最简单的想法就是从头到尾遍历一次,如果数组下标和下标对应项目不相等,就退出循环。这种解法的代码如下:
int solve(int* a, int aLen ) { // write code here int i = 0; while (1) { if (a[i] != i) { break; } i+=1; } return i; }
这种算法的问题就是,输入的数组越大,程序的执行时间越长,时间复杂度是O(n),但是符合题目的要求。
这道题还有一个思路就是二分查找,其实我拿到题目的第一感觉就是查找那个索引和值不相等的项目,二分查找的时间复杂度是O(LogN),优于O(N)。
int solve2(int* a, int aLen) { int left = 0; int right = aLen - 1; int mid; while (right >= left) { mid = (left + right) / 2; // 证明了mid右边是连续的,将left右移 if (a[mid] == mid) { left = mid + 1; } else { right = mid - 1; } } return left; }