力扣-268题丢失的数字（C++）- 原地哈希+有价值

╰+哭是因爲堅強的太久メ 2022-08-28 10:59 178阅读 0赞

题目链接：[https://leetcode-cn.com/problems/missing-number/][https_leetcode-cn.com_problems_missing-number]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
解法一：原地哈希

class Solution {
        
    public:
        int missingNumber(vector<int>& nums) {
        
            
            for(int i=0;i<nums.size();i++){
        
                while(nums[i]<nums.size()&&nums[i]!=nums[nums[i]]){
        
                    swap(nums[i],nums[nums[i]]);
                }
            }
    
            for(int i=0;i<nums.size();i++){
        
                if(nums[i]!=i) return i;
            }
    
            return nums.size();
        }
    };

解法二：数学公式直接算

class Solution {
        
    public:
        int missingNumber(vector<int>& nums) {
        
            int n=nums.size();//数组中存放了n-1个数
            int real_sum=(n+1)*(0+n)/2;
            int sum=0;
    
            for(auto e:nums)
                sum+=e;
            
            return real_sum-sum;
        }
    };

[https_leetcode-cn.com_problems_missing-number]: https://leetcode-cn.com/problems/missing-number/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d915f74f841e4c7c88163550a45417f9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/427e9a49ab64471da3027c63f1ddf5c7.png