题解 | #缺失数字#

思路

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

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

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