位運算 · ttttt

# 位運算 # 位運算我這里總結了幾道位運算的題目分享給大家，分別是 136和137， 260 和 645，總共加起來四道題。四道題全部都是位運算的套路，如果你想練習位運算的話，不要錯過哦～～ ## 前菜開始之前我們先了解下異或，后面會用到。 1. 異或的性質兩個數字異或的結果`a^b`是將 a 和 b 的二進制每一位進行運算，得出的數字。運算的邏輯是果同一位的數字相同則為 0，不同則為 1 1. 異或的規律 2. 任何數和本身異或則為`0` 3. 任何數和 0 異或是`本身` 4. 異或運算滿足交換律，即： `a ^ b ^ c = a ^ c ^ b` OK，我們來看下這三道題吧。 ## 136. 只出現一次的數字1 題目大意是除了一個數字出現一次，其他都出現了兩次，讓我們找到出現一次的數。我們執行一次全員異或即可。 ``` <pre class="calibre18">``` class Solution: def singleNumber(self, nums: List[int]) -> int: single_number = 0 for num in nums: single_number ^= num return single_number ``` ``` ***復雜度分析*** - 時間復雜度：O(N)O(N)O(N)，其中N為數組長度。 - 空間復雜度：O(1)O(1)O(1) ## 137. 只出現一次的數字2 題目大意是除了一個數字出現一次，其他都出現了三次，讓我們找到出現一次的數。靈活運用位運算是本題的關鍵。 Python3: ``` <pre class="calibre18">``` class Solution: def singleNumber(self, nums: List[int]) -> int: res = 0 for i in range(32): cnt = 0 # 記錄當前 bit 有多少個1 bit = 1 <# 記錄當前要操作的 bit for num in nums: if num & bit != 0: cnt += 1 if cnt % 3 != 0: # 不等于0說明唯一出現的數字在這個 bit 上是1 res |= bit return res - 2 ** 32 if res > 2 ** 31 - 1 else res ``` ``` - 為什么Python最后需要對返回值進行判斷？如果不這么做的話測試用例是\[-2,-2,1,1,-3,1,-3,-3,-4,-2\] 的時候，就會輸出 4294967292。其原因在于Python是動態類型語言，在這種情況下其會將符號位置的1看成了值，而不是當作符號“負數”。這是不對的。正確答案應該是 - 4，-4的二進制碼是 1111...100，就變成 2^32-4=4294967292，解決辦法就是減去 2 \*\* 32 。 > 之所以這樣不會有問題的原因還在于題目限定的數組范圍不會超過 2 \*\* 32 JavaScript: ``` <pre class="calibre18">``` var singleNumber = function(nums) { let res = 0; for (let i = 0; i < 32; i++) { let cnt = 0; let bit = 1 << i; for (let j = 0; j < nums.length; j++) { if (nums[j] & bit) cnt++; } if (cnt % 3 != 0) res = res | bit; } return res; }; ``` ``` ***復雜度分析*** - 時間復雜度：O(N)O(N)O(N)，其中N為數組長度。 - 空間復雜度：O(1)O(1)O(1) ## 645. 錯誤的集合和上面的`137. 只出現一次的數字2`思路一樣。這題沒有限制空間復雜度，因此直接hashmap 存儲一下沒問題。不多說了，我們來看一種空間復雜度O(1)O(1)O(1)的解法。由于和`137. 只出現一次的數字2`思路基本一樣，我直接復用了代碼。具體思路是，將nums的所有索引提取出一個數組idx，那么由idx和nums組成的數組構成singleNumbers的輸入，其輸出是唯二不同的兩個數。但是我們不知道哪個是缺失的，哪個是重復的，因此我們需要重新進行一次遍歷，判斷出哪個是缺失的，哪個是重復的。 ``` <pre class="calibre18">``` class Solution: def singleNumbers(self, nums: List[int]) -> List[int]: ret = 0 # 所有數字異或的結果 a = 0 b = 0 for n in nums: ret ^= n # 找到第一位不是0的 h = 1 while(ret & h == 0): h <<= 1 for n in nums: # 根據該位是否為0將其分為兩組 if (h & n == 0): a ^= n else: b ^= n return [a, b] def findErrorNums(self, nums: List[int]) -> List[int]: nums = [0] + nums idx = [] for i in range(len(nums)): idx.append(i) a, b = self.singleNumbers(nums + idx) for num in nums: if a == num: return [a, b] return [b, a] ``` ``` ***復雜度分析*** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 260. 只出現一次的數字3 題目大意是除了兩個數字出現一次，其他都出現了兩次，讓我們找到這個兩個數。我們進行一次全員異或操作，得到的結果就是那兩個只出現一次的不同的數字的異或結果。我們剛才講了異或的規律中有一個`任何數和本身異或則為0`，因此我們的思路是能不能將這兩個不同的數字分成兩組 A 和 B。分組需要滿足兩個條件. 1. 兩個獨特的的數字分成不同組 2. 相同的數字分成相同組這樣每一組的數據進行異或即可得到那兩個數字。問題的關鍵點是我們怎么進行分組呢？由于異或的性質是，同一位相同則為 0，不同則為 1. 我們將所有數字異或的結果一定不是 0，也就是說至少有一位是 1. 我們隨便取一個，分組的依據就來了，就是你取的那一位是 0 分成 1 組，那一位是 1 的分成一組。這樣肯定能保證`2. 相同的數字分成相同組`, 不同的數字會被分成不同組么。很明顯當然可以，因此我們選擇是 1，也就是說`兩個獨特的的數字`在那一位一定是不同的，因此兩個獨特元素一定會被分成不同組。 ``` <pre class="calibre18">``` class Solution: def singleNumbers(self, nums: List[int]) -> List[int]: ret = 0 # 所有數字異或的結果 a = 0 b = 0 for n in nums: ret ^= n # 找到第一位不是0的 h = 1 while(ret & h == 0): h <<= 1 for n in nums: # 根據該位是否為0將其分為兩組 if (h & n == 0): a ^= n else: b ^= n return [a, b] ``` ``` ***復雜度分析*** - 時間復雜度：O(N)O(N)O(N)，其中N為數組長度。 - 空間復雜度：O(1)O(1)O(1) ## 相關題目 - [number-of-1-bits](https://leetcode-cn.com/problems/number-of-1-bits/) - [counting-bits](https://leetcode-cn.com/problems/counting-bits/) - [reverse-bits](https://leetcode-cn.com/problems/reverse-bits/) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經30K star啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。