Pythonでリストの中から被っている値を見つけよう！！LeetCodeの解法例あり

• リストの中から被っている値を見つけよう！！
• 基本
  • 問題
  • 解法
    • 改良前
    • 改良後

リストの中から被っている値を見つけよう！！

という話。

見つけてその値を削除するなり、被っている値の数を数えるなり、被っている値は何なのかを返すなりは別にいいとして、個人的な方法をメモ代わりに取っておく。

基本

今回は考えやすいようにLeetCodeの問題を例に考えてみます。

問題

例えばこちら。
287. Find the Duplicate Number

難易度はMediumです。

問題としては与えられた数字のみのリストの中に1つだけ2つ存在する値があるのでそちらを探して欲しいという問題です。
例としては以下のような感じ。

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1,1]
Output: 1

Example 4:

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

解法

改良前

これの解放としてパッと思い浮かぶものとしては、二つのfor文で二つの値を比較しながら被っている値があれば行いたい処理を行う、というもの。

ただ、与えられたリストがソートされていないのでまずソートしないとその比較はできなくなります。

試しにPython3で書いてみました。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        ans = 0
        nums = sorted(nums)
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i] == nums[j]:
                    ans = nums[i]
        return ans
# Time Limit Exceeded

計算量はO(n^2)です。

試しに実行してみましたが、これでは時間切れです。

改良後

ではどうするのか？
この上のコードを少し改良するだけで実は計算量を大きく改善できます。

それが以下のコードです。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        if not nums:
            return
        ans,index = 0,1
        nums = sorted(nums)
	    for i in range(1,len(nums)):
	        if nums[i] == nums[index-1]:
	            ans = nums[i]
		    else:
		        index += 1
        return ans
# Runtime: 68 ms, faster than 55.74% of Python3 online submissions for Find the Duplicate Number.
# Memory Usage: 16.6 MB, less than 78.10% of Python3 online submissions for Find the Duplicate Number.

二重for文の後のfor文を事前にインデックス値として宣言します。

for文の中で仮に値が被っていなければインデックスの値を1プラスするだけ。
被っていれば値をansに追加してインデックスの値を1プラスする。

これだけで計算量がO(n)になります。
そしてO(n^2)だと時間切れだったものが通るようになります。

こんな感じです。
単純な工夫ですが、これだけで計算量を削減できるので手軽に使えますね。

今回のメモはこんな感じ。