力扣-剑指 Offer 53 - II. 0~n-1中缺失的数字（C++）- 二分法+有价值&&非二分

系统管理员 2022-09-09 04:38 87阅读 0赞

题目链接：[https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/][https_leetcode-cn.com_problems_que-shi-de-shu-zi-lcof]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
解法一：二分法  
思路：  
![在这里插入图片描述][f569ec990c814a19a5225aa532009778.png]

class Solution {
        
    public:
        int missingNumber(vector<int>& nums) {
        
            int size=nums.size();
            if(size==0) return 0;
    
            int low=0,high=size-1,mid;
    
            while(low<high){
        
                mid=(low+high)/2;
                if(nums[mid]!=mid) high=mid;  //[L,R]->[L,M]
                else low=mid+1;   //nums[mid]==mid;[L,R]->[M+1,R]
            }
            
            if(nums[high]==high) high++;//整个序列是从0~n-1，丢失的数字为n
    
            return high;
        }
    };

解法二：非二分法

class Solution {
        
    public:
        int missingNumber(vector<int>& nums) {
        
            int sum=0;
            for(const auto &e:nums){
        
                sum+=e;
            }
    
            int len=nums.size();
            int realsum=len*(len+1)/2;
    
            return realsum-sum;
            // int n=nums.size();
            // int sum=0;
            // for (const auto &e : nums) {
        
            //     sum += e;
            // }
            // int realSum=n*(n+1)/2;
            // return realSum - sum;
        }
    };

[https_leetcode-cn.com_problems_que-shi-de-shu-zi-lcof]: https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/3332f10f62604988b8a91544f40dbd8b.png
[f569ec990c814a19a5225aa532009778.png]: /images/20220829/29aaa6a266e74515a745dfd3c9794ce9.png