本博客记录一些比较经典的题目和优秀的解法

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次.求出现一次的元素

• 方法1

  考虑到每个元素都只出现一次或两次，所以最终结果的和应该为sum=2a+2b+…+n,所以我们只要求得sum1=a+b+c+…+n 用2*sum1-sum就等于只出现一次的元素。

  代码：

  int singleNumber(int a[], int n){   
     set<int> hashSet;     
     int sum = 0, sum1 = 0;         
     for(int i = 0; i < n; i++){         
         hashSet.insert(a[i]);         
         sum += a[i];         
     }         
     for(auto it = hashSet.begin(); it != hashSet.end(); it++){         
         sum1 += *it;         
     }          
     return sum1 * 2 - sum;         
  }
  

• 方法2。

  巧妙地使用异或，利用a^a = 0的结论，将数组中所有元素异或，剩下的就是单独元素，该方法可以推广到一个元素出现奇数次，其它数出现偶数次。

  代码：

  int singleNumber(int a[], int n){    
     int res = a[0];     
     for(int i = 0; i < n; i++){    
         res ^= a[i];     
     }    
     return res;     
  }     

给你一个长度为 n 的数组，其中只有一个数字出现了大于等于 n/2 次，问如何使用优秀的时空复杂度快速找到这个数字。

• 方法

先假设result是第一个数，然后从第二个数开始遍历，遇见相同的就+1，不同的就-1，如果count==0，就result赋值为下一个数，接着遍历，最后result的值 就是结果。该方法的思想是众数一定比其他所有的数加起来的数量要多，就算是众数与其他每一个数相抵消，最后剩下来的也是众数。况且还有其他数之间的抵消，所以剩下来的一定是众数。

• 代码：

  int findNumber(int a[], int n){     
     int res = a[0], count = 1;    
     for(int i = 0; i < n; i++){    
         count = result == a[i] ? ++count : --count;      
         if(count == 0){;    
             res = a[i+1];     
         }      
     }    
     return res;    
  }