leetcode 17.04 消失的数字

一、题目描述

二、解题思路

(1)将向量从小到大排序之后，目标位置可以把向量划分为两个不同的部分，目标位置及其右侧的位置，元素值大于下标值，目标位置左侧的位置，元素值等于下标值，具有“二段性”，因此可以使用二分法来解决这个问题；

(2)目标位置即为合法区间(元素值大于下标值的区间)的左边界，查找左边界即可。若left==nums[left]，则说明消失的是最后一个数字，返回nums.size()即可。

三、代码实现

时间复杂度：T(n)=O(n)

空间复杂度：S(n)=O(1)

class Solution {
public:int missingNumber(vector<int>& nums) {//二分法查找左边界sort(nums.begin(),nums.end());int left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]==mid) left=mid+1;else if(nums[mid]>mid) right=mid;}if(left==nums[left]) return nums.size();else return left;}
};