RSSフィードを購読
Python Coding Challenge - How will you identify a single number in an array?
(Python コーディングチャレンジ [リスト内の唯一重複していない要素を見つけよう！] 編)
(Python コーディングチャレンジ [リスト内の唯一重複していない要素を見つけよう！] 編)
問題自体はそれほど難しくないと思いますが、様々なアプローチで解決してみましょう。List を利用する、dictionary を利用する、Python の collections モジュールを利用する、数学的なアプローチを採る、という方法を試します。
Python のデータ構造を操作する良い練習になるはずです。
問題：
int 値を要素とするリスト nums が与えられます。このリストの要素は同じものが必ず２つ含まれていますが、ただ１つだけ１つしか含まれていない要素が存在します。この要素を探し出して返すプログラムを記述してください。
例：
与えられるリスト nums: [2, 5, 1, 2, 5]
# 出力: 1
例の解説：
2 と 5 は２つずつ含まれていますが 1 は１つしか含まれていません。よって 1 を返します。
また関数定義は以下のような形です (同じである必要はありません):
def single_number(nums: list[int]) -> int:
...
...
作成したプログラムは以下のテストをパスする必要があります:
import unittest
class TestSingleNumber(unittest.TestCase):
def test_1(self):
nums = [10, 10, 7]
res = single_number(nums)
self.assertEqual(res, 7)
def test_2(self):
nums = [2, 5, 1, 2, 5]
res = single_number(nums)
self.assertEqual(res, 1)
if __name__ == '__main__':
unittest.main()
class TestSingleNumber(unittest.TestCase):
def test_1(self):
nums = [10, 10, 7]
res = single_number(nums)
self.assertEqual(res, 7)
def test_2(self):
nums = [2, 5, 1, 2, 5]
res = single_number(nums)
self.assertEqual(res, 1)
if __name__ == '__main__':
unittest.main()
考え方:
冒頭にも述べたように様々なアプローチを試してみましょう。最初は list を利用してみます。
アプローチ1: list の利用
方法は単純です。空のリスト uniques を用意しておきます。与えられたリスト nums の要素をループで走査していき、uniques に含まれていなければ追加し、含まれていれば削除します。最終的に残っているものが答えになります。
def single_number(nums: list[int]) -> int:
uniques = []
for i in nums:
if i in uniques:
uniques.remove(i)
else:
uniques.append(i)
return uniques[0]
uniques = []
for i in nums:
if i in uniques:
uniques.remove(i)
else:
uniques.append(i)
return uniques[0]
Complexity Analysis
(アルゴリズム解析)
Time complexity (実行計算時間):
与えられたリストの要素数 n 分のループを実行します。また、それぞれのループにおいて、内部で保持しているリスト uniques の要素数分のループが発生します。この操作は最悪で n 回起こり得ますから最悪計算時間は O(n) です。よってプログラム全体の実行計算時間は O(n²) です。
Space complexity (実行メモリ要求量):
最悪 n 個の要素を保持するリスト uniques を新たに作成しています。よって実行メモリ要求量は O(n) です。
アプローチ 2: dictionary の利用
続いて dictionary を利用する方法を考えてみましょう。今回は key が含まれていない場合でもエラーを発生させずに新たなアイテムに初期値を割り当てて作成してくれる collections モジュールの defaultdict を利用します。
今回は要素の数をカウントしたいので、dictionary の key に対する value は int 値になります。よって defaultdict には初期値を作成する場合のファクトリ関数として int を指定します。そうすることで、存在しない key が指定された場合に value が 0 に初期化された要素が自動的に追加されるようになります:
from collections import defaultdict
def single_number(nums: list[int]) -> int:
nums_dict = defaultdict(int)
for i in nums:
nums_dict[i] += 1
return min(nums_dict, key=nums_dict.get)
def single_number(nums: list[int]) -> int:
nums_dict = defaultdict(int)
for i in nums:
nums_dict[i] += 1
return min(nums_dict, key=nums_dict.get)
Complexity Analysis
(アルゴリズム解析)
Time complexity (実行計算時間):
与えられたリストの要素数 n 分のループを実行します。また、出現した回数が 1 の要素を探すために min() を利用しています。この関数の最悪計算時間は O(n) です。よってプログラム全体の実行計算時間は O(n + n) となり結果的に O(n) です。
Space complexity (実行メモリ要求量):
最悪 n 個の要素を保持する defaultdict を新たに作成しています。よって実行メモリ要求量は O(n) です。
アプローチ 3: collections モジュールの Counter クラスの利用
続いて同じく collections モジュールに含まれている Counter クラスを利用してみます。
Counter は dict のサブクラスです。イテラブル、もしくは、マッピングオブジェクトを受け取り、その中に出現する要素の数をカウントした dictionary 様のオブジェクトを返してくれます。また most_common() メソッドを利用することでカウント数の大きい要素順に並べ替えた (key, value) というタプルから成るリストを返してくれます。
ですから most_common() で返されたリストの最後の要素が出現回数が最も少なかった要素、この問題では回数 1 の要素ですから、その tuple の最初の要素を返せばよい、ということになります。このプログラムは１行で実装可能です:
from collections import Counter
def single_number(nums: list[int]) -> int:
return Counter(nums).most_common()[-1][0]
def single_number(nums: list[int]) -> int:
return Counter(nums).most_common()[-1][0]
Complexity Analysis
(アルゴリズム解析)
Time complexity (実行計算時間):
与えられたリストの要素数を n とすると、Counter 自体はそのすべての要素をループしますから O(n) です。また、most_common() のソートアルゴリズムの最悪計算時間は O(n log n) となっています。よってプログラム全体の実行計算時間は O(n + n log n)、結果的に O(n log n) です。
Space complexity (実行メモリ要求量):
最悪 n 個の要素を保持する Counter オブジェクトを新たに作成しています。よって実行メモリ要求量は O(n) です。
アプローチ 4: 数学的手法の利用
最後に数学的な少し面白いアプローチをご紹介します。
与えられるリスト nums が [1, 1, 2, 2, 3, 3, 4] としましょう。この時 nums の重複しない要素からなるリスト nums_unique [1, 2, 3, 4] を考えます。
この時 nums_unique の各要素を２倍した和を求めると 1*2 + 2*2 + 3*2 + 4*2 = 20 となります。また nums の要素の総和は 1*2 + 2*2 + 3*2 + 4 = 16 となります。つまり、(nums_unique * 2) - (nums * 2) が答えである 4 になっている、ということです。
この考え方をプログラムとして実装するには、リスト内のユニークな要素からなる集合を求める必要がありますが、これは set() を利用すれば大丈夫ですよね。続いて総和を求めるには sum() が使えます。ですからこのプログラムも実は１行で実装できてしまいます:
def single_number(nums: list[int]) -> int:
return sum(set(nums)) * 2 - sum(nums)
return sum(set(nums)) * 2 - sum(nums)
Complexity Analysis
(アルゴリズム解析)
Time complexity (実行計算時間):
与えられたリストの要素数を n とすると、set() も sum() もそれぞれの実行計算時間は O(n) です。よってプログラム全体では O(n + n)、結果的に O(n) です。
Space complexity (実行メモリ要求量):
最悪 n/2 個の要素を保持する set を新たに作成しています。よって実行メモリ要求量は O(n/2) です。