当前位置：网站首页>Missing number

Missing number

2022-07-03 00:02:00 【wx58c8fa5d0b356】

Missing number

subject

Given an inclusion 0, 1, 2, …, n in n Sequence of Numbers , find 0 … n The number that does not appear in the sequence .

Example

       
         Example  1:
        

        
 Input : [3,0,1]
        
 Output : 2
        

        
 Example  2:
        
 Input : [9,6,4,2,3,5,7,0,1]
        
 Output : 8
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.

Problem solving

Ideas

There are two simple and feasible schemes , One is to use bit operations , One is to solve problems with mathematical methods

An operation

       
        #  The algorithm of XOR bit operation 
        
1. a ⊕ a = 0
        
2. a ⊕ b = b ⊕ a
        
3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;
        
4. d = a ⊕ b ⊕ c  Can be launched  a = d ⊕ b ⊕ c.
        
5. a ⊕ b ⊕ a = b.
        

        
 If the length of the array is n, So it's actually asking （0 - n.length） The missing number in the range 
        

        
 We put （0 - n.length） All numbers XOR up nums All values in the array , Finally, it is actually the solution sought .
        

        
 Because two identical numbers XOR equals 0,0 I wonder if any number on the list is still that number .
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.

Mathematical methods

       
         We put （0 - n.length） Sum all the numbers , And then subtract it in turn nums Values in the array , The final result is what you want .
       
       
        1.

Time complexity is O（n）, The space complexity is O（1）

Code

An operation

       
        class Solution {
        
    public int missingNumber(int[] nums) {
        
        int sum = ((nums.length) * (nums.length + 1)) / 2;
        

        
        for (int num : nums) {
        
            sum -= num;
        
        }
        
        return sum;
        
    }
        
}
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.

Mathematical methods

       
        class Solution {
        
    public int missingNumber(int[] nums) {
        
        int missing = nums.length;
        
        for (int i = 0; i < nums.length; i++) {
        
            missing ^= i ^ nums[i];
        
        }
        
        return missing;
        
    }
        
}
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.