題目資訊

• 題目編號: 217
• 題目連結: Contains Duplicate
• 主題: Array, Hash Table, Sorting

題目敘述

給定一個整數數組 nums，如果任何數值在數組中至少出現兩次，則返回 true，如果每個元素都不相同，則返回 false。

範例1:

輸入: nums = [1,2,3,1]

輸出: true

解釋:

元素 1 在索引 0 和 3 出現。

範例2:

輸入: nums = [1,2,3,4]

輸出: false

解釋:

所有元素都是不相同的。

範例3:

輸入: nums = [1,1,1,3,3,4,3,2,4,2]

輸出: true

限制條件:

• $1 \leq \text{nums.length} \leq 10^5$
• $-10^9 \leq \text{nums}[i] \leq 10^9$

直覺

這個問題要求我們檢查整數數組 nums 中是否存在重複元素。解決此問題的一個直接方法是利用已排序數組的特性：任何重複的元素在數組排序後將是相鄰的。這種理解引導我們先對數組進行排序，然後尋找連續且相同的元素。

解法

演算法遵循以下步驟：

1. 特殊情況處理：如果數組僅包含一個元素，那麼立即得出結論數組中沒有重複元素，因此返回 false。這一步可被視作優化，旨在避免不必要的計算。

2. 排序數組：使用排序函數對輸入數組 nums 進行排序。排序後，可能存在的任何重複元素現在將排列在相鄰位置。

3. 檢查重複元素：遍歷排序後的數組，檢查連續元素。如果發現任意兩個連續元素相等，這表示存在重複元素，函數立即返回 true。

4. 最終結論：如果遍歷整個數組後未找到連續且相同的元素，則函數得出結論沒有重複元素，返回 false。

該演算法主要依賴於排序過程的效率，其時間複雜度為 $O(n \log n)$，其中 $n$ 是數組中的元素數量。隨後對重複元素的線性掃描時間複雜度為 $O(n)$，因此排序步驟是計算時間的主要因素。此方法通過利用排序數組的特性來有效地檢查是否存在重複元素。

程式碼

C++

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // 如果只有一個元素，我們不可能有重複
        if (nums.size() == 1) {
            return false;
        }
        
        // 排序陣列以將任何重複項集合在一起
        sort(nums.begin(), nums.end());
        
        // 遍歷陣列以檢查連續的重複元素
        for (int i = 0; i < nums.size() - 1; i++) {
            // 如果兩個連續的元素相同，則找到了重複項
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        
        // 如果沒有找到重複項，返回 false
        return false;
    }
};

Python

class Solution:
    def containsDuplicate(self, nums):
        # 如果只有一個元素，不可能有重複的
        if len(nums) == 1:
            return False
        
        # 將數組排序，以便將任何重複的元素放在一起
        nums.sort()
        
        # 遍歷數組以檢查連續的重複元素
        for i in range(len(nums) - 1):
            # 如果兩個連續元素相同，則找到一個重複的元素
            if nums[i] == nums[i + 1]:
                return True
        
        # 如果沒有找到重複的元素，返回false
        return False

複雜度分析

• 時間複雜度: 主要操作為對陣列進行排序和遍歷。排序操作主導了時間複雜度，其時間複雜度為 $O(n \log n)$，其中 $n$ 為陣列 nums 中的元素數量。遍歷陣列以檢查重複項的時間複雜度為 $O(n)$。因此，整體時間複雜度為 $O(n \log n)$。
• 空間複雜度: 如果我們不考慮排序算法使用的空間，則空間複雜度為 $O(1)$，因為排序操作是就地進行的。然而，如果排序函數使用了額外的空間，則空間複雜度將取決於 sort 所使用的排序算法。在大多數標準庫的實現中，遞歸調用期間的堆疊空間的輔助空間為 $O(\log n)$。