力扣面试题 17.04. 消失的数字(求和,位运算)

Problem: 面试题 17.04. 消失的数字

文章目录

题目描述

思路

思路1:求和

先求取1-n的数字和,再减去数组中所有元素的和即为缺失数

思路2:位运算

我们利用异或运算的特性:相同位为0,不同位为1;0与仍何数异或后得到仍何数,即我们先另一个变量(初始为0)与数字1-n异或,再次与数组中的所有元素异或,最后得到的值则为所缺失的元素;

复杂度

思路1与思路2的时间何空间复杂度均如下
时间复杂度:

      O 
     
    
      ( 
     
    
      n 
     
    
      ) 
     
    
   
     O(n) 
    
   
 O(n)

空间复杂度:

      O 
     
    
      ( 
     
    
      1 
     
    
      ) 
     
    
   
     O(1) 
    
   
 O(1)

Code

思路1:

classSolution{public:/**
     * Bit operation
     * @param nums Given array
     * @return int
     */intmissingNumber(vector<int>&nums){int n = nums.size();int res =0;for(int i =0; i <= n;++i){
            res ^= i;}for(int i =0; i < n;++i){
            res ^= nums[i];}return res;}};

思路2:

classSolution{public:/**
     * Maths
     * @param nums Given array
     * @return int
     */intmissingNumber(vector<int>&nums){int n = nums.size();int res =0;for(int i =0; i <= n;++i){
            res += i;}for(int i =0; i < n;++i){
            res -= nums[i];}return res;}};