【LeetCode】136. Single Number 解答・解説【Python】

問題
1. 原
2. 内容
方針
解答
1. 解答1：
2. 解答2：
補足・参考・感想

問題

原

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

　Input: nums = [2,2,1]

　Output: 1

Example 2:

　Input: nums = [4,1,2,1,2]

　Output: 4

Example 3:

　Input: nums = [1]

　Output: 1

Constraints:

1 <= nums.length <= 3 * 10⁴

-3 * 10⁴ <= nums[i] <= 3 * 10⁴

Each element in the array appears twice except for one element which appears only once.

内容

空でない整数の要素を持つリストnumsが与えられます。1つの要素を除いて、全ての要素は2度出現します。1回のみ出現する要素を見つけてください。

時間計算量が線形時間(O(n))であり、定数空間(O(1))で実装しなければなりません。

※正しくない可能性があります。

方針

・Xor演算を使用する

・もしくは、重複除外後に各要素を2倍にしたリストから、元のリストの各要素を除外する

解答

解答1：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        #重複除外後に各要素を2倍したリストを作成
        _ = list(set(nums))*2
        #上記リストからnumsの各要素を除外
        for i in nums:
            _.remove(i)
        #最後に残った要素を返す
        return _[0]

class Solution:

def singleNumber(self, nums: List[int]) -> int:

#重複除外後に各要素を2倍したリストを作成

_ = list(set(nums))*2

#上記リストからnumsの各要素を除外

for i in nums:

_.remove(i)

#最後に残った要素を返す

return _[0]

・setで重複を除外

・listでリストに変換

・リストにしてから*2とすることで各要素を2つに増やす

・上記のリストは全ての要素が2回出現するものになる

・元のリストは1つを除いて各要素は2回出現するため、上記のリストから元のリストの各要素を除外した後、最後に残った要素を返すと答えになる。

・時間計算量はO(n)なので問題ないが、空間計算量がO(n)となるため、指定された解法ではない。

解答2：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        xor = 0
        for num in nums:
            xor ^= num
        return xor