《剑指offer》面试题53 - II. 0～n-1中缺失的数字

问题描述

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]

输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]

输出: 8

限制：

1 <= 数组长度 <= 10000

代码

class Solution {

public:

    int missingNumber(vector<int>& nums) {

        int n = nums.size(),sum = (n*(n+1))/2;

        for(int num:nums)

        {

            sum -= num;

        }

        return sum;

    }

};

结果

执行用时 :44 ms, 在所有 C++ 提交中击败了20.68%的用户

内存消耗 :17.3 MB, 在所有 C++ 提交中击败了100.00%的用户

代码

class Solution {

public:

    int missingNumber(vector<int>& nums) {

        int n = nums.size(),i;

        for(i = 0; i < n; ++i)

        {

            if(nums[i]!=i)

                break;

        }

        return i;

    }

};

结果

执行用时 :44 ms, 在所有 C++ 提交中击败了20.68%的用户

内存消耗 :17.3 MB, 在所有 C++ 提交中击败了100.00%的用户

代码

使用二分法，如果\(nums[middle] == middle\)说明从\([0,middle]\)是正常的，缺少的值在\([middle+1,right]\),如果\(nums[middle] ！= middle\)说明从\([middle,right]\)已经发生了错位，因此缺少的值在\([left,middle]\)之间。最后要注意的是返回值，很有可能\(0\)到\(n-1\)之间没有缺失，缺少数字\(n\)要特别考虑。

class Solution {

public:

    int missingNumber(vector<int>& nums) {

        int n = nums.size(),left = 0,right = n-1,middle;

        while(left < right)

        {

            middle = left + (right - left)/2;

            if(nums[middle] == middle)

            {

                left = middle + 1;

            }

            else

                right = middle;

        }

        return left == n-1 && nums[left]==left?left+1:left;

    }

};

结果

执行用时 :40 ms, 在所有 C++ 提交中击败了32.99%的用户

内存消耗 :17.3 MB, 在所有 C++ 提交中击败了100.00%的用户

巴特西

《剑指offer》面试题53 - II. 0～n-1中缺失的数字

问题描述

代码

代码

代码

最新文章

热门文章