溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

leetcode怎么查看數組中重復的數字

發布時間:2022-01-17 13:38:47 來源:億速云 閱讀:199 作者:小新 欄目:大數據
# LeetCode怎么查看數組中重復的數字

## 引言

在算法學習和編程面試中,**查找數組中重復數字**是一個經典且高頻出現的問題。這類問題不僅考察基礎編程能力,更檢驗開發者對數據結構、算法效率的掌握程度。本文將系統性地講解在LeetCode環境中解決數組重復數字問題的多種方法,涵蓋從暴力解法到最優算法的完整思路,幫助讀者建立系統的解題框架。

## 問題定義與示例

### 基本問題描述
給定一個長度為n的整數數組,數組中所有數字都在0~n-1范圍內。找出數組中任意一個重復的數字。

**示例1:**
```python
輸入:[2, 3, 1, 0, 2, 5, 3]
輸出:2或3

變種問題

  1. 不修改原數組找出重復數字(LeetCode 287)
  2. 找出所有重復數字(LeetCode 442)
  3. 數字范圍在1~n之間(與索引偏移相關)

方法一:暴力雙重循環(時間復雜度O(n2))

實現原理

通過兩層循環逐個比較數組元素。

def findDuplicate(nums):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] == nums[j]:
                return nums[i]

復雜度分析

  • 時間復雜度:O(n2)
  • 空間復雜度:O(1)

適用場景

僅在小規模數據時可用,LeetCode中通常會超時。

方法二:哈希表法(時間復雜度O(n))

實現原理

利用哈希表存儲已出現過的數字。

def findDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return num
        seen.add(num)

復雜度分析

  • 時間復雜度:O(n)
  • 空間復雜度:O(n)

優勢與局限

  • 優點:邏輯簡單,適用于各種變種問題
  • 缺點:需要額外空間,不符合某些題目要求

方法三:排序+遍歷(時間復雜度O(nlogn))

實現步驟

  1. 先對數組排序
  2. 遍歷比較相鄰元素
def findDuplicate(nums):
    nums.sort()
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            return nums[i]

復雜度分析

  • 時間復雜度:O(nlogn)(主要來自排序)
  • 空間復雜度:取決于排序實現

方法四:原地交換法(時間復雜度O(n))

核心思想

利用數組索引和值的對應關系,通過交換元素到正確位置來發現重復。

def findDuplicate(nums):
    i = 0
    while i < len(nums):
        if nums[i] == i:
            i += 1
        else:
            if nums[nums[i]] == nums[i]:
                return nums[i]
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]

關鍵點解析

  1. 每個數字應位于與值相同的索引處
  2. 交換時發現目標位置已有正確值則說明重復

復雜度分析

  • 時間復雜度:O(n)(每個元素最多被交換兩次)
  • 空間復雜度:O(1)

方法五:二分查找法(時間復雜度O(nlogn))

適用場景

特別適用于LeetCode 287(不修改數組且空間O(1))

實現原理

基于鴿巢原理,統計小于等于mid的數的個數。

def findDuplicate(nums):
    left, right = 1, len(nums)-1
    while left < right:
        mid = (left + right) // 2
        count = sum(1 for num in nums if num <= mid)
        if count > mid:
            right = mid
        else:
            left = mid + 1
    return left

復雜度分析

  • 時間復雜度:O(nlogn)(需要進行logn次遍歷)
  • 空間復雜度:O(1)

方法六:快慢指針法(時間復雜度O(n))

Floyd判圈算法應用

將數組視為鏈表,用快慢指針找環的入口。

def findDuplicate(nums):
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    
    finder = 0
    while finder != slow:
        finder = nums[finder]
        slow = nums[slow]
    return finder

算法圖解

Phase 1: 確定相遇點
2→3→1→0→2→3→1...
slow: 2→1→3→0→2
fast: 2→3→0→1→3→0→1→3...

Phase 2: 找環入口
finder: 0→2→1
slow:   2→1→3

復雜度分析

  • 時間復雜度:O(n)
  • 空間復雜度:O(1)

不同方法的對比總結

方法 時間復雜度 空間復雜度 是否修改原數組 適用場景
暴力循環 O(n2) O(1) 小數據量
哈希表 O(n) O(n) 通用解法
排序+遍歷 O(nlogn) O(1) 允許修改且不限空間
原地交換 O(n) O(1) 數字范圍在0~n-1
二分查找 O(nlogn) O(1) 1~n范圍且不修改數組
快慢指針 O(n) O(1) 存在且僅存在一個重復數

LeetCode實戰題目解析

題目287. 尋找重復數

要求:給定包含n+1個整數的數組,其數字在1到n之間(包括1和n),假設只有一個重復的整數,找出這個重復的數。

最優解

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # 快慢指針解法
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
                
        finder = 0
        while finder != slow:
            finder = nums[finder]
            slow = nums[slow]
        return finder

題目442. 數組中重復的數據

要求:找出所有出現兩次的元素。

解法

def findDuplicates(nums):
    res = []
    for num in nums:
        idx = abs(num) - 1
        if nums[idx] < 0:
            res.append(abs(num))
        else:
            nums[idx] = -nums[idx]
    return res

常見錯誤與調試技巧

  1. 索引越界問題

    • 檢查數字范圍與數組長度的關系
    • 示例:當數字范圍是1~n時,訪問nums[n]會導致越界
  2. 無限循環

    • 快慢指針解法必須確保有重復數存在
    • 添加循環次數限制作為保護措施
  3. 邊界條件

    # 測試用例
    [1,1]        # 最小重復
    [2,2,2,2]    # 多個重復
    [1,3,4,2,2]  # 標準情況
    

進階思考

  1. 如果要求返回所有重復數字且空間復雜度為O(1)?
  2. 當數組元素是對象而非數字時如何解決?
  3. 海量數據情況下(內存放不下)如何處理?

總結

掌握查找數組重復數字的多種解法,有助于培養以下能力: - 根據題目約束選擇最優算法 - 理解時間空間復雜度的權衡 - 靈活運用數據結構特性

建議按照以下順序練習: 1. 先實現哈希表解法 2. 再嘗試原地交換 3. 最后攻克快慢指針解法

提示:在LeetCode做題時,注意題目中的關鍵約束條件,如”不能修改原數組”、”空間復雜度O(1)“等,這些往往是解題方法的選擇關鍵。 “`

(注:實際字數約2200字,此處顯示為精簡版框架,完整文章需展開各部分的詳細說明和代碼注釋)

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

亚洲午夜精品一区二区_中文无码日韩欧免_久久香蕉精品视频_欧美主播一区二区三区美女