【剑指offer】面试题53-Ⅱ：0～n-1中缺失的数字——二分查找

方法一：二分查找法

class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        int left = 0;
        int right = nums.size() - 1;

        while( left <= right )
        {
    
            int mid = left + ( right - left ) / 2;
            if( nums[mid] == mid )
            {
    
                left = mid + 1;
            }
            else
            {
    
                right = mid - 1;
            }
        }
        return left;

    }

};

方法二：异或

0-n-1个数，与0-n异或可以得到最终的结果

class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        int flag = 0;
        for( int i = 0; i < nums.size(); i++ )
        {
    
            flag ^= nums[i];
        }
        for( int i = 0; i <= nums.size(); i++)
        {
    
            flag ^= i;
        }
        return flag;
    }
};

方法三：0-n相加减去数组中的数