leetcode 136. Single Number

Seawolf

1. Given a non-empty array of integers, every element appears twice except for one. Find that single one.
   
2. 
   
3. Note:
   
4. 
   
5. Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
   
6. 
   
7. Example 1:
   
8. 
   
9. Input: [2,2,1]
   
10. Output: 1
    
11. Example 2:
    
12. 
    
13. Input: [4,1,2,1,2]
    
14. Output: 4

复制代码

1. class Solution {
   
2.     public int singleNumber(int[] nums) {
   
3.         
   
4.         if(nums.length == 0) return 0;
   
5.         
   
6.         if(nums.length == 1) return  nums[0];
   
7.         
   
8.         Arrays.sort(nums);
   
9.         
   
10.         for(int i = 1; i< nums.length;i++ ){
    
11.             
    
12.             if(nums[i] == nums[i-1]) continue;
    
13.             
    
14.             else{
    
15.                 if(i == nums.length-1) return nums[i];
    
16.                
    
17.                 if(i == 1) return nums[i-1];
    
18.                
    
19.                 if(nums[i] == nums[i+1]) i++;
    
20.                
    
21.                 else{ return nums[i]; }
    
22.             }
    
23.         }
    
24.         
    
25.         
    
26.         return 0;
    
27.     }
    
28. }

复制代码

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

复制代码