一個數(shù)組中只有一個數(shù)字出現(xiàn)奇數(shù)次门烂，其他都是出現(xiàn)偶數(shù)次粟害，時間復(fù)雜度為O(n);

/**
 * Author: Taoyongpan
 * Date: Created in 9:35 2018/6/14
 * 一個數(shù)組中只有一個數(shù)只出現(xiàn)了奇數(shù)次甚疟，其他都是出現(xiàn)偶數(shù)次茫陆，時間復(fù)雜度為O(n)
 */
public class Test10 {
    public static void main(String[] args) {
        int[] arr = {1,1,2,3,4,2,3,};
        int res = arr[0];
        for (int i = 1 ; i< arr.length;i++){
            res^=arr[i];
        }
        System.out.println(res);
    }
}

一個數(shù)字有兩個數(shù)出現(xiàn)奇數(shù)次其他都是出現(xiàn)偶數(shù)次

/**
 * Author: Taoyongpan
 * Date: Created in 9:42 2018/6/14
 * 數(shù)組中只出現(xiàn)一次的兩個數(shù)字
 * 方法金麸，將 兩個不同的數(shù)分別放置到兩個數(shù)組中，
 * 通過二進(jìn)制的某一位簿盅，是0或者1將整個數(shù)組拆分開
 */
public class Test12 {
    public static void main(String[] args) {
        int[] arr = {1,1,2,3,4,2,};
        int res = 0;
        int j = 0;
        int num1 = 0;
        int num2 = 0;
        for (int i = 0 ; i < arr.length ; i++ ){
            res^=arr[i];
        }
        for (j = 0 ;j < 32;j++){
            if (((res>>j)&0)==0){
                break;
            }
        }
        for (int i = 0;i<arr.length;i++){
            if (((arr[i]>>j)&1)==1)
                num1^=arr[i];
            else
                num2^=arr[i];
        }
        System.out.println(num1);
        System.out.println(num2);
    }
}

一個數(shù)組中只有一個數(shù)出現(xiàn)一次挥下，其他都是出現(xiàn)三次，輸出這個數(shù)：

/**
* Author: Taoyongpan
* Date: Created in 9:38 2018/6/14
* 一個數(shù)組中只有一個數(shù)字出現(xiàn)了一次 桨醋，其他都是出現(xiàn)了三次棚瘟，
* 在O(n)的時間復(fù)雜度中，求出這個只出現(xiàn)一次的數(shù)
* 解法：當(dāng)一個數(shù)組每一個數(shù)都出現(xiàn)三次的時候喜最，二進(jìn)制表示上面每一位 1的個數(shù)肯定是三的倍數(shù)偎蘸，
* 當(dāng)不是三的倍數(shù)的時候，說明只出現(xiàn)一次的那個數(shù)此位上為1
*/
public class Test11 {
  public static void main(String[] args) {
      int[] a = {1,1,1,2,2,2,3};
      int[] bits = new int[32];
      for (int i = 0; i < a.length; i++)
          for (int j = 0; j < 32; j++)
              bits[j] += ((a[i] >> j) & 1);
      int res = 0;
      for (int j = 0; j < 32; j++)
          if (bits[j] % 3 != 0)
              res += (1 << j);
      System.out.println(res);
  }
}