0~n-1缺失的数字(注意尾巴也有可能)

题目简单，提供多种解法，嘻嘻！

• 解法一：推荐的

class Solution{
public:
    int missingNumber(vector<int>& nums)
    {       
        //[0,2,3]  缺1
        for(int i=0;i<nums.size();i++)
        {
        	if(nums[i]!=i) return i;
        }
        //尾巴[0,1,2]  缺3
        return nums.size();
    }
};
//========================================进行进一步优化
class Solution{
public:
    int missingNumber(vector<int>& nums)
    {       
         //[0,2,3]  缺1
        if(nums[nums.size()-1]!=nums.size()-1)
        {
            for(int i=0;i<nums.size();i++)
            {
                if(nums[i]!=i) return i;
            }
        }
        //尾巴[0,1,2]  缺3
        return nums.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 解法二：有序的序列，主要考的还是二分的思想

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int low=0;
        int high=nums.size()-1;
        //[1,2,3]  缺4
        if(nums[high]==high) return high+1;

        //包含[0] 缺1   和 [0,1,3] 缺2--正常情况
        while(low<high)
        {
            int mid=(low+high)>>1;
            if(nums[mid]==mid) low=mid+1;
            else high=mid;
        }
        return low;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 解法三：这种特殊的情况，可以采用公式（n项求和-目前数组总和）

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        //缺尾
        if(nums[nums.size()-1]==nums.size()-1) return nums.size(); 
        int max=nums[0];
        int min=nums[0];
        for(int aa:nums)
        {
            if(max<aa) max=aa;
            if(min>aa) min=aa;
        }
        int gongshi=(max+min)*(max-min+1)/2;//求和公式
        int sum=0;
        for(int aa:nums)
        {
            sum+=aa;
        }  
        return gongshi-sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21