題目
找出數(shù)組中重復(fù)的數(shù)字。
在一個(gè)長(zhǎng)度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)法挨。數(shù)組中某些數(shù)字是重復(fù)的陈症，但不知道有幾個(gè)數(shù)字重復(fù)了叉寂，也不知道每個(gè)數(shù)字重復(fù)了幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字翁逞。
示例 1：
輸入： [2, 3, 1, 0, 2, 5, 3] 輸出：2 或 3
限制:
2 <= n <= 100000
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有肋杖。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處挖函。
解法
1. 超時(shí)解法
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
超時(shí)解法
magic = -12323
for i in range(len(nums)):
num = nums[i]
nums[i] = magic
if num in nums:
return num
這是最容易想到的解法状植，每次拿到一個(gè)數(shù)，都去原始的數(shù)組里面看看有沒(méi)有其他的挪圾。同時(shí)為了不讓自己和自己混淆浅萧，把這個(gè)數(shù)變成一個(gè)魔數(shù)，但是很遺憾超時(shí)了哲思。
2. 排序算法
def findRepeatNumber(self, nums: List[int]) -> int:
# 利用內(nèi)置的sort函數(shù)
nums.sort()
for i in range(len(nums)-1):
if nums[i] == nums[i+1]:
return nums[i]
那么，不如首先對(duì)數(shù)組進(jìn)行排序吩案，這里的排序比如用快拍堆排就行了棚赔，為了方便我直接用了python內(nèi)置的排序，雖然過(guò)了徘郭，但是為了找一個(gè)數(shù)對(duì)整個(gè)數(shù)組排序還是有點(diǎn)無(wú)用功靠益。
3. hashset
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
# 哈希set解法
tmp = set()
for i in nums:
if i in tmp:
return i
else:
tmp.add(i)
因?yàn)閔ashset內(nèi)的元素具有唯一性，而且hashset的復(fù)雜度較低残揉，那我們從數(shù)組中取出數(shù)字加入到hashset中胧后，如果發(fā)生了沖突就說(shuō)明找到了。
4. 利用數(shù)組作為哈希表
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
# 注意到限定條件：在一個(gè)長(zhǎng)度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)抱环。
# 那就可以自己【手動(dòng)】建立一個(gè)長(zhǎng)度為n的“哈希表”壳快，對(duì)應(yīng)關(guān)系是n->n
table = [-1]*len(nums)
for i in nums:
if table[i] == i:
return i # 發(fā)生了沖突
else:
table[i] = i # 加入表
5. 不需要重新開(kāi)辟空間的解
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
# 開(kāi)辟數(shù)組其實(shí)沒(méi)有必要，我們可以在原有數(shù)組上進(jìn)行操作
# 思路對(duì)了镇草，但是方法不對(duì)眶痰，這樣的循環(huán)不能保證：比如i = 0 的位置是0
# for i in range(len(nums)):
# if nums[i] != i:
# if nums[nums[i]] == nums[i]:
# return nums[i]
# else:
# nums[i],nums[nums[i]] = nums[nums[i]],nums[i]
# 正確的
i = 0
while i < len(nums):
if nums[i] != i : # 如果下標(biāo)和值不對(duì)應(yīng)，那么這個(gè)數(shù)字就應(yīng)該放在正確的位置
if nums[i] != nums[nums[i]]: # 放過(guò)去的數(shù)字上
# 交換
# nums[i],nums[nums[i]] = nums[nums[i]],nums[i]
t = nums[i]
nums[i],nums[t] = nums[t],nums[i]
else:
return nums[i]
else:
i += 1
我們可以知道梯啤，在n個(gè)元素的數(shù)組上竖伯，放下0~n-1的數(shù)字。如果沒(méi)有重復(fù)的話因宇，按照從小到大的順序排列就是[0,1,2,3,4,5...,n-1]七婴。
所以我們可以通過(guò)交換數(shù)組中元素的順序，來(lái)還原為：數(shù)組上每個(gè)數(shù)字的位置就是該數(shù)組元素的值察滑，也就是在第0個(gè)位置值為0打厘，第一個(gè)元素值為1...
6. bonus 不修改數(shù)組的，不使用額外存儲(chǔ)空間
TODO
