[LeetCode] [Python] 260。シングルナンバーIII
260
数字の配列numsが与えられ、正確に2つの要素が1回だけ表示され、他のすべての要素が正確に2回表示されます。一度だけ現れる2つの要素を見つけます。
例えば：
nums = [1、2、1、3、2、5]の場合、[3、5]を返します。
注意：
- 結果の順序は重要ではありません。したがって、上記の例では、[5、3]も正しいです。
- アルゴリズムは、線形実行時間計算量で実行する必要があります。一定のスペースの複雑さのみを使用して実装できますか？
アイデア：私は長い間問題を解決していませんでした、そして私は考えがないことに気づきました。
まず、Pythonのセットは、繰り返されない要素の順序付けられていないセットです。基本的な機能には、リレーショナルテストと繰り返される要素の削除が含まれます。コレクションオブジェクトは、和集合、共通部分、差、対称差もサポートします。したがって、ここでは、このセットの機能を使用できます。 2つのセットを使用して、numsファサードのデータを別々に配置します。セットにすでに1つある場合は、もう1つ入れます。 2つの違いは私たちが求めるものです。
次に、またはを使用します。numsのすべての数値にXORを使用する場合、他の繰り返される値のXORの結果は0になるため、最終結果はリクエストのXORの結果になります。次に、の結果を確認します。 2つのXOR。一部のXORの結果が1の場合、その位置で2つの数値が異なることを意味します。
次に、すべての番号を2つのグループに分割します。一方は対応する位置にあり、もう一方は対応する位置にありません。 2つの異なる数字が私たちが探しているものです。
ヒント：diff＆= -diff
#!/usr/bin/env python # -*- coding: UTF-8 -*- class Solution(object): def singleNumber(self, nums): ''' :type nums: List[int] :rtype: List[int] ''' one = set() double = set() for n in nums: if n not in one: one.add(n) else: double.add(n) print one print double return list(one - double) def singleNumber2(self, nums): diff = 0 for n in nums: diff ^= n #Get its last set bit diff &= -diff res = [0, 0] for n in nums: if(n&diff==0): res[0] ^= n else: res[1]^=n return res if __name__ == '__main__': sol = Solution() nums = [1, 2, 1, 3, 2, 5] print sol.singleNumber(nums) print sol.singleNumber2(nums)