思路

这道题的输入是一个等差数列,当然其中缺失了一项。

最简单的想法就是从头到尾遍历一次,如果数组下标和下标对应项目不相等,就退出循环。这种解法的代码如下:

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;
}