面試題56 - I. 陣列中數字出現的次數
題目
一個整型陣列 nums 里除兩個數字之外，其他數字都出現了兩次，請寫程式找出這兩個只出現一次的數字，要求時間復雜度是O(n)，空間復雜度是O(1)，
示例 1：
輸入：nums = [4,1,4,6]
輸出：[1,6] 或 [6,1]
示例 2：
輸入：nums = [1,2,10,4,1,4,3,3]
輸出：[2,10] 或 [10,2]
限制：
- 2 <= nums <= 10000
解題思路
思路：異或，位運算
先說下異或的性質：二進制位同一位相同則為 0，不同則為 1，
再說說一下異或的規律：
- 若兩數值相同，兩者的異或結果為 0，（即是任何數與自身異或結果為 0）
- 任何數與 0 異或結果為本身
同時異或是滿足交換律，結合律的（數學符合：⊕）
- 交換律： a ⊕ b = b ⊕ a
- 結合律： a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
回來看本題，題目說明，【整型陣列 nums 中，除兩個數字之外，其他數字都出現了兩次】，那么根據交換律、結合律將相同數字進行異或運算，那么相同數字都會變為 0，再根據第二條規律，那么剩下的出現一次的數字，
在這里主要需要實作的如何確保將陣列分成兩組，使得：
- 只出現一次的數字，在不同的兩組；
- 相同的陣列出現在相同的組，
只有這樣，每組進行異或運算的時候，最終才會剩下單獨的數字，那么該如何進行分組？特別是如何將兩個不同的數字分到不同的組？
具體實作代碼如下，
代碼實作
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
res = 0
# 全員進行異或
for num in nums:
res ^= num
# 找出不為 0 的最低位
# & 位運算的使用
div = 1
while (div & res == 0):
div <<= 1
# 進行分組
p, q = 0, 0
for num in nums:
if num & div:
p ^= num
else:
q ^= num
return [p, q]
實作結果
以上就是使用異或，位運算的思路，解決《面試題56 - I. 陣列中數字出現的次數》問題的主要內容，題目主要的難度在于如何對陣列進行分組，然后根據異或的規律性質進行求解，
歡迎關注微信公眾號《書所集錄》
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/151722.html
標籤：Python
上一篇：【2020Python修煉記】python綜合專案（三）Virus專案
下一篇：c語言商品管理系統問題