LeetCode 136.一度しか現れない数字(python)
タイトルリンク
タイトルの説明:
空でない整数配列が与えられ、ある要素が1回しか現れない以外は、各要素が2回現れます.それが一度しか現れなかった要素を見つけます.
説明:
あなたのアルゴリズムは線形時間の複雑さを持つべきです.余分なスペースを使わずに実現できますか?
例1:
入力:[2,2,1]出力:1例2:
入力:[4,1,2,1,2]出力:4解題構想:配列を遍歴し,各要素の出現回数を計算し,1であればその数を出力する(この方法は時間がかかりすぎる)
p.s.他人のやり方は、異或で配列を処理し、異或はビット異或の2つの数で、相異は1で、同じは0である.他の要素の出現回数はいずれも2回であるため、2回の異和を経た後もaの値は変わらず、最後に0に相当して1回の数字と異和する.
タイトルの説明:
空でない整数配列が与えられ、ある要素が1回しか現れない以外は、各要素が2回現れます.それが一度しか現れなかった要素を見つけます.
説明:
あなたのアルゴリズムは線形時間の複雑さを持つべきです.余分なスペースを使わずに実現できますか?
例1:
入力:[2,2,1]出力:1例2:
入力:[4,1,2,1,2]出力:4解題構想:配列を遍歴し,各要素の出現回数を計算し,1であればその数を出力する(この方法は時間がかかりすぎる)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
for i in nums:
if nums.count(i)==1:
return i
p.s.他人のやり方は、異或で配列を処理し、異或はビット異或の2つの数で、相異は1で、同じは0である.他の要素の出現回数はいずれも2回であるため、2回の異和を経た後もaの値は変わらず、最後に0に相当して1回の数字と異和する.
a = 0
for n in nums:
a = a ^ n
return a