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

この記事は約3分で読めます。

 

問題

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 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 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:

 

・setで重複を除外

・listでリストに変換

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

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

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

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

解答2:

・解説を見てもわからない。

・Xorの演算から勉強する必要あり。

 

 

補足・参考・感想

参考

計算量まで含めて一番詳しい解説。Xorの解説も書いてくれているのだけど理解できない。。。

Think it through || Time: O(n) Space: O(1) || Python Explained – Single Number – LeetCode

 

 

前:119. Pascal’s Triangle II

次:141. Linked List Cycle

LeetCode 解答・解説記事一覧

コメント