劍指offer-40、數組中只出現⼀次的數字詳情 - 後端 sevencoding 博客

題⽬描述

⼀個整型數組⾥除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現⼀次的數字。

示例
輸入：[92,3,43,54,92,43,2,2,54,1]
輸出：3，1

思路解答

哈希表統計

使⽤ hashmap 存儲數字出現的次數， key 為出現的數字， value 為該數字出現的次數。遍歷⾥⾯所有的數字，如果 hashmap 中存在，那麼 value （次數）+1，如果 hashmap 中不存在,那麼 value 置為1。

遍歷完成之後，需要將次數為 1 的數字撈出來，同樣是遍歷 hashmap ，由於只有兩個滿⾜條件，我們設置⼀個標識變量，初始化為1，如果找到第⼀個滿⾜條件的數字，除了寫⼊放回數組中，還需要將該標識置為 2 ，表示接下來找的是第 2 個。

如果找到第 2 個，那麼寫⼊之後，直接 return 。

public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
     Map<Integer, Integer> maps = new HashMap<>();
     if (array != null) {
         for (int n : array) {
             Integer num = maps.get(n);
             if (num == null) {
                 // map中不存在
                 maps.put(n, 1);
             } else {
                 // map中已經存在
                 maps.put(n, num + 1);
             }
         }
      }
      int index = 1;
      for (Map.Entry<Integer, Integer> entry : maps.entrySet()) {
          if (entry.getValue() == 1) {
             if (index == 1) {
                 num1[0] = entry.getKey();
                 index++;
             } else {
                 num2[0] = entry.getKey();
                 return;
             }
         }
     }
 }

時間複雜度：O(n)，需要遍歷數組兩次
空間複雜度：O(n)，需要HashMap存儲頻率信息

排序遍歷

先對數組排序，然後遍歷查找不連續的數字。排序後相同的數字會相鄰，遍歷找到不連續的數字

public class Solution {

    public int[] FindNumsAppearOnce(int[] nums) {
        if (nums == null || nums.length < 2) {
            return new int[0];
        }
        
        // 對數組進行排序
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        
        int[] result = new int[2];
        int index = 0;
        
        // 遍歷查找不連續的數字
        for (int i = 0; i < sorted.length; i++) {
            // 檢查當前數字是否與前後都不同
            boolean isSingle = true;
            
            // 檢查前一個元素（如果不是第一個元素）
            if (i > 0 && sorted[i] == sorted[i - 1]) {
                isSingle = false;
            }
            
            // 檢查後一個元素（如果不是最後一個元素）
            if (i < sorted.length - 1 && sorted[i] == sorted[i + 1]) {
                isSingle = false;
            }
            
            if (isSingle) {
                result[index++] = sorted[i];
                if (index == 2) break; // 找到兩個數字後退出
            }
        }
        
        // 確保結果按升序排列
        if (result[0] > result[1]) {
            int temp = result[0];
            result[0] = result[1];
            result[1] = temp;
        }
        
        return result;
    }
}

時間複雜度：O(nlogn)，主要來自排序操作
空間複雜度：O(1) 或 O(n)，取決於是否克隆數組

位運算（最優解）

⾸先需要了解⼀定位運算知識，異或是指⼆進制中，⼀個位上的數如果相同結果就是0，不同則結果是0.

也就是如果⼀個數的最低位是0，另⼀個數的最低位是0，那麼異或結果的最低位是0；如果⼀個數的最低位是0，另⼀個數的最低位是1，那麼異或結果的最低位是1。

異或操作可以交換，不影響結果：A^BC = A^BC

A^A=0,任何⼀個數異或⾃身，等於0，因為所有位都相同

A^0 = A，任何⼀個數異或0，等於⾃身，因為所有位如果和0不同，就是1，也就是保留了⾃身的數值

假設⾥⾯出現⼀次的兩個元素為 A 和 B ，初始化異或結果 res 為0，遍歷數組⾥⾯所有的數，都進⾏異或操作，則最後結果 res = A^B 。

但是我們拿到這個 A 和 B 異或之後的結果，怎麼區分呢？

有⼀種巧妙的思路，因為 A 和 B 的某⼀位不同才會在結果中出現 1 ，説明在那⼀位上， A 和 B 中肯定有⼀個是 0 ，有⼀個是 1 。

那我們取出異或結果 res 最低位的1，假設這個數值是 temp （temp只有⼀個位是1，也就是A和B最後不同的位）

遍歷數組中的元素，和 temp 進⾏與操作，如果和 temp 相與，不等於0。説明這個元素的該位上也是1。那就説明它很有可能就是 A 和 B 中的⼀個。

只是有可能，其他的數也有可能該位上為 1 。但是符合這種情況的，其他數肯定出現兩次，⽽ A 和 B只可能有⼀個符合，並且只有可能出現⼀次 A 或者 B 。

凡是符合和 temp 相與,結果不為0的，我們進⾏異或操作。

也就是可能出現， res1 = B^CD^CD...^EE^B 或者 res1 = A^CD^CD...^EE 。

上⾯的式⼦可以視為 res1 = B 或者 res1 = A

這樣操作下來，我們就知道了 res1 肯定是其中⼀個只出現⼀次的數（ A 或者 B ）,⽽同時上⾯計算出了 res = A^B ,也就是可以通過 res1^res 求出另⼀個數。

public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
     // A和B異或的結果
     int res = 0;
     for (int val : array) {
     	res ^= val;
     }
    
     // temp保存了兩個數最後⼀個不同的位
     int temp = res & (-res);
     // 保存和最後⼀個不同的位異或的結果
     int res1 = 0;
     for (int val : array) {
         // 不等於0説明可能是其中⼀個數，⾄少排除了另外⼀個數
         if ((temp & val) != 0) {
         	res1 ^= val;
         }
     }
     // 由於其他滿⾜條件的數字都出現兩次，所以結果肯定就是隻出現⼀次的數
     num1[0] = res1;
     // 求出另外⼀個數
     num2[0] = res ^ res1;
 }

時間複雜度：O(n)，只需要遍歷數組兩次
空間複雜度：O(1)，只使用固定數量的變量

位運算原理解析

通過示例詳細解釋算法過程：

輸入：[92,3,43,54,92,43,2,2,54,1]
單次數：3 和 1

步驟1：計算所有數字的異或結果

92 ^ 3 ^ 43 ^ 54 ^ 92 ^ 43 ^ 2 ^ 2 ^ 54 ^ 1
= (92 ^ 92) ^ (43 ^ 43) ^ (2 ^ 2) ^ (54 ^ 54) ^ 3 ^ 1
= 0 ^ 0 ^ 0 ^ 0 ^ (3 ^ 1)
= 3 ^ 1 = 2

步驟2：找到異或結果的最低位的1

3的二進制: 0011
1的二進制: 0001
3^1=2的二進制: 0010
最低位的1在從右往左第2位（值為2）

步驟3：根據最低位1分組

第1組（第2位為0）：3(0011), 43(101011), 54(110110), 1(0001), 92(1011100)
第2組（第2位為1）：2(0010)

步驟4：分別異或各組

第1組: 3 ^ 43 ^ 54 ^ 1 ^ 92 ^ 43 ^ 54 ^ 92
     = (3 ^ 1) ^ (43 ^ 43) ^ (54 ^ 54) ^ (92 ^ 92) 
     = 3 ^ 1 = 2 ❌ 這裏應該是 3 ^ 1 = 2，但我們需要重新計算正確的分組

讓我們重新正確分組計算：
實際分組應該是：
第1組（第2位為0）：3, 1  // 只有這兩個數在第2位為0且是單次數
第2組（第2位為1）：所有其他數

正確的計算：
第1組: 3 ^ 1 = 2
第2組: 92 ^ 43 ^ 54 ^ 92 ^ 43 ^ 2 ^ 2 ^ 54 = 0

位運算特性利用：

相同數字異或為0：a ^ a = 0
任何數與0異或為本身：a ^ 0 = a
異或滿足交換律和結合律

sevencoding 博客

sevencoding 博客

博客 / 詳情