Leetcode 217. Contains Duplicate

Problem

配列に重複要素があるのかどうかを判定するシンプルな問題です。

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

InputとOutputの例は次になります。

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

Key Idea

一番シンプルなアイデアとしては、二重でループして各要素を比較するという方法が考えられます。ただし、その場合は計算量がかかってTLEになってしまうため、別の方法を検討する必要があります。
ここでは、Sortを使う方法、Hashtableを使う方法 x 2を紹介します。

Approach #1 : Brute-force

最もシンプルに、それぞれの要素を比較していきます。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False

ただし、上述の通り、この解法では、計算量が大きく、TLE(Time Limit Exceeded)となってしまいます。

• Time complexity: O(N^2)

• Space complexity: O(1)

Approach #2 : Sorting

ソートを使ってこの問題を解く方法もあります。具体的には、リストをソートした後、隣り合う要素が同じかどうかをチェックすることで重複を検出します。例えば、[1,2,3,1]を[1,1,2,3]にすると、隣同士の要素の比較するだけで重複判定をすることができます。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return True
        return False

まずリストnumsをソートします。そして、ソートされたリストの要素を順番に見ていき、ある要素が前の要素と同じだった場合はTrueを返します。全ての要素を見終わっても重複がなければFalseを返します。
計算量は、下記の様になります。

• Time complexity: O(n log n)。リストをソートするために必要な時間が主となります。Pythonの組み込みソート関数は通常O(n log n)の時間がかかります。
• Space complexity: O(1)。リストのソートはインプレース（元のリスト内で）行われ、隣接する要素の比較もインプレースで行いますので、追加の空間を必要としません。

Approach #1よりは効率が良くなったことがわかります。ただし、sort処理が時間的にはボトルネックとなっています。Trade offではありますが、Space complexityを犠牲にすると、更にTime complexityを改善させることができます。

Approach #3 : HashSet

Hashsetを使うと、要素の検索と追加を使って重複の検出ができます。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashset = set()
        for num in nums:
            if num in hashset:
                return True
            else:
                hashset.add(num)
        return False

• Time complexity: O(n)。Setへの要素の検索と追加はO(1)で、n回繰り返すため、全体としてはO(n)になります。
• Space complexity: O(n)。リストの全ての要素を保持する新たなSetを作成しますので、リストのサイズに比例します。

Approach #4 : HashSet'

HashSetを使うと、もし重複があったときには要素数が減ることに着目することもできます。

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        hashset = set()
        if len(set(nums)) == len(nums):
            return False
        else:
            return True

計算量はApproach #3と変わりません。

Reference