LeetCode #217 Contains Duplicate 包含重複項目

LeetCode題目翻譯

英文原文如下

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.

中文翻譯

給予一個整數陣列 nums,要是陣列中有任意值出現兩次以上就回傳 true ,如果全部元素都是唯一的話回傳 false

範例及題目限制


解題思路

這一題應該不用特別說明,就挺明確的,要看array當中有沒有重複的值

C# 解決方案

❌不推薦的解決方法

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        for(int i = 0;i<nums.Length;i++)
        {
            if(Array.IndexOf(nums, nums[i],i+1)!=-1)
            {
                return true;
            }
        }
        return false;
    }
}

這我想到的第一個解決方案,用for loop搭配上IndexOf 去逐步判斷

送出去後,卻發現有點太慢了

時間複雜度 :  O(n2) ➡ Array.IndexOf ≈ O(n) * For 迭代 O(n)

方案1HashSet

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        HashSet<int> hSet = new HashSet<int>();
        
        for(int i = 0;i<nums.Length;i++)
        {
            if(hSet.Contains(nums[i]))
            {
                return true;
            }
            hSet.Add(nums[i]);
        }
        return false;
    }
}

這次用到的是HashSet,也就是雜湊,類似Dictionary

時間複雜度 :  O(n) ➡ HashSet.Contains ≈ O(1) * For 迭代 O(n)

方案2Array.Sort

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        Array.Sort(nums);
        
        for(int i = 0;i<nums.Length-1;i++)
        {
            if(nums[i]==nums[i+1])
            {
                return true;
            }
        }
        return false;
    }
}

這個解決方法就比較有趣了,將Array整個排列後

直接比較前後值,要是出現重複就回傳 true

時間複雜度 : O(n2 log n)Array.Sort O(n log n)   * For 迭代 O(n)

⭐Array.Sort的速度會因應陣列的狀況而有所改變,這裡的是其平均速度

Java解決方案

方案1 – HashSet

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> hSet = new HashSet<Integer>();
        
        for(int i = 0;i<nums.length;i++)
        {
            if(hSet.contains(nums[i]))
            {
                return true;
            }
            hSet.add(nums[i]);
        }
        return false;
    }
}

Python3 解決方案

方案1 – set

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

方案1.1 – 當然也能改用dict

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        d = {}  #dict
        
        for i in range(len(nums)):
            if(nums[i] in d):
                return True
            d[nums[i]] = 0
            
        return False

JavaScript 解決方案

方案1

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    var set = new Set();
    for(var i = 0;i<nums.length;i++)
    {
        if(set.has(nums[i]))
        {
            return true;
        }
        set.add(nums[i]);
    }
    return false;
};

方案2 – 先sort

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort();
    for(var i=0; i<nums.length-1;i++)
    {
        if(nums[i] == nums[i+1]) 
        {
            return true;
        }
    }
    return false;
};

結論

其實這一題算是考驗基本功吧,懂得越多種型別,能解決的方式就越多種!

而速度也會因為不同的變數、function特性而有所變化

🧡如果這篇文章有幫上你的一點點忙,那是我的榮幸

🧡收藏文章或幫我分享,我都會很感謝的

✅如有任何疑問,歡迎透過留言或messenger讓我知道 !

題目連結 : Contains Duplicate – LeetCode

一些隨機文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *