一、題目描述

給你一個整數數組?nums?，除某個元素僅出現?一次?外，其余每個元素都恰出現?三次 。請你找出并返回那個只出現了一次的元素。

你必須設計并實現線性時間復雜度的算法且使用常數級空間來解決此問題。

示例 1：

輸入：nums = [2,2,3,2]
輸出：3

示例 2：

輸入：nums = [0,1,0,1,0,1,99]
輸出：99

提示：

• 1 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• nums?中，除某個元素僅出現?一次?外，其余每個元素都恰出現?三次

二、解題思路

這個問題是一個典型的位操作問題。由于每個元素都出現了三次，除了一個元素只出現了一次，我們可以考慮每個元素的每一位。如果將所有元素在每個位上累加起來，那么每個位上的和應該是3的倍數。如果有任何位上的和不是3的倍數，那么只出現一次的元素在該位上必須是1。

例如，假設數組是?[2,2,3,2]（二進制表示為?[10, 10, 11, 10]）：

• 在第一位（最右邊）上，所有數的和是 1+1+1+1 = 4，不是3的倍數，這意味著只出現一次的數的第一位是1。
• 在第二位上，所有數的和是 0+0+1+0 = 1，不是3的倍數，這意味著只出現一次的數的第二位是1。

所以，只出現一次的數是?11，即 3。

我們可以用這樣的方法檢查每個位，然后重構出只出現一次的數。

以下是具體的解題步驟：

1. 初始化一個長度為32的數組（因為一個整數的二進制表示最多有32位）來存儲每一位的和。
2. 遍歷數組?nums?中的每個數，對于每個數，檢查其二進制表示的每一位，如果是1，則將對應位的和加1。
3. 遍歷完成后，檢查每一位的和，如果不是3的倍數，那么只出現一次的數在該位上是1。
4. 根據這些信息，重構出只出現一次的數。

三、具體代碼

class Solution {public int singleNumber(int[] nums) {int[] count = new int[32]; // 32位整數for (int num : nums) {for (int i = 0; i < 32; i++) {count[i] += (num >> i) & 1; // 檢查num的第i位是否為1}}int result = 0;for (int i = 0; i < 32; i++) {// 如果count[i]不是3的倍數，那么result的第i位是1result |= (count[i] % 3) << i;}return result;}
}

四、時間復雜度和空間復雜度

1. 時間復雜度

• 遍歷數組?nums?中的每個元素是一個 O(n) 操作，其中 n 是數組?nums?的長度。
• 對于每個元素，我們檢查它的每一位，這是一個 O(1) 操作，因為一個整數的位數是固定的，最多為 32 位。
• 因此，外層循環的時間復雜度是 O(n)，內層循環的時間復雜度是 O(1)，所以總的時間復雜度是 O(n)。

2. 空間復雜度

• 我們使用了一個長度為 32 的數組?count?來存儲每一位的和，這是一個固定大小的數組，不隨輸入數組?nums?的大小而變化。
• 因此，空間復雜度是 O(1)，即常數空間復雜度。

綜上所述，給定代碼的時間復雜度是 O(n)，空間復雜度是 O(1)。這滿足了題目要求的線性時間復雜度和常數空間復雜度。

五、總結知識點

1. 位操作：

• >>：右移操作符，用于將一個數的二進制表示向右移動指定的位數。例如，num >> i?表示將?num?的二進制表示向右移動?i?位。
• &：按位與操作符，用于對兩個數的二進制表示進行逐位比較，只有兩個位都是1時，結果位才是1。在這里，(num >> i) & 1?用于檢查?num?的第?i?位是否為1。
• |：按位或操作符，用于對兩個數的二進制表示進行逐位比較，只要有一個位是1，結果位就是1。在這里，result |= (count[i] % 3) << i?用于將?result?的第?i?位設置為1，如果?count[i] % 3?不為0。

2. 數組的初始化和使用：

• int[] count = new int[32];：初始化一個長度為32的整數數組，用于存儲每一位的和。

3. 循環結構：

• for (int num : nums)：這是Java中的增強型for循環，用于遍歷數組?nums?中的每個元素。
• for (int i = 0; i < 32; i++)：這是一個傳統的for循環，用于重復執行32次，每次循環處理一個二進制位。

4. 取模運算：

• %：取模運算符，用于計算一個數除以另一個數后的余數。在這里，count[i] % 3?用于檢查?count[i]?是否是3的倍數。

5. 位掩碼：

• 1 << i：創建一個只在第?i?位上為1的位掩碼。這個掩碼用于將?count[i] % 3?的結果放到?result?的正確位置上。

以上就是解決這個問題的詳細步驟，希望能夠為各位提供啟發和幫助。