leetcode 268. Missing Number

Seawolf

1. Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
   
2. 
   
3. Example 1:
   
4. 
   
5. Input: [3,0,1]
   
6. Output: 2
   
7. Example 2:
   
8. 
   
9. Input: [9,6,4,2,3,5,7,0,1]
   
10. Output: 8
    
11. Note:
    
12. Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

复制代码

1. class Solution {
   
2.     public int missingNumber(int[] nums) {
   
3.         int max = Integer.MIN_VALUE;
   
4.         for(int i:nums){
   
5.             
   
6.             if(i > max) max = i;
   
7.         }
   
8.         
   
9.         int[] re = new int[max+1];
   
10.         
    
11.         for(int i = 0 ; i< nums.length; i++){
    
12.             
    
13.             re[nums[i]]++;
    
14.         }
    
15.         
    
16.         for(int i = 0; i< re.length ; i++){
    
17.             
    
18.             if(re[i] == 0) return i;
    
19.         }
    
20.         
    
21.         return max+1;
    
22.         
    
23.     }
    
24. }

复制代码

1. class Solution {
   
2.     public int missingNumber(int[] nums) {
   
3.         
   
4.         int sum = 0, max =nums[0];
   
5.         for(int i:nums){
   
6.             
   
7.             sum += i;
   
8.             if(i > max) max =i;
   
9.         }
   
10.         
    
11.         int total = nums.length * (nums.length+1)/2;
    
12.         
    
13.         return total - sum;
    
14.         
    
15.     }
    
16. }

复制代码