# LeetCode怎么查看數組中重復的數字
## 引言
在算法學習和編程面試中,**查找數組中重復數字**是一個經典且高頻出現的問題。這類問題不僅考察基礎編程能力,更檢驗開發者對數據結構、算法效率的掌握程度。本文將系統性地講解在LeetCode環境中解決數組重復數字問題的多種方法,涵蓋從暴力解法到最優算法的完整思路,幫助讀者建立系統的解題框架。
## 問題定義與示例
### 基本問題描述
給定一個長度為n的整數數組,數組中所有數字都在0~n-1范圍內。找出數組中任意一個重復的數字。
**示例1:**
```python
輸入:[2, 3, 1, 0, 2, 5, 3]
輸出:2或3
通過兩層循環逐個比較數組元素。
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]
僅在小規模數據時可用,LeetCode中通常會超時。
利用哈希表存儲已出現過的數字。
def findDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)
def findDuplicate(nums):
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
return nums[i]
利用數組索引和值的對應關系,通過交換元素到正確位置來發現重復。
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]]
特別適用于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
將數組視為鏈表,用快慢指針找環的入口。
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(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) | 否 | 存在且僅存在一個重復數 |
要求:給定包含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
要求:找出所有出現兩次的元素。
解法:
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] # 最小重復
[2,2,2,2] # 多個重復
[1,3,4,2,2] # 標準情況
掌握查找數組重復數字的多種解法,有助于培養以下能力: - 根據題目約束選擇最優算法 - 理解時間空間復雜度的權衡 - 靈活運用數據結構特性
建議按照以下順序練習: 1. 先實現哈希表解法 2. 再嘗試原地交換 3. 最后攻克快慢指針解法
提示:在LeetCode做題時,注意題目中的關鍵約束條件,如”不能修改原數組”、”空間復雜度O(1)“等,這些往往是解題方法的選擇關鍵。 “`
(注:實際字數約2200字,此處顯示為精簡版框架,完整文章需展開各部分的詳細說明和代碼注釋)
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。