題目描述
在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)杉辙。 數(shù)組中某些數(shù)字是重復(fù)的特愿，但不知道有幾個數(shù)字是重復(fù)的配并。也不知道每個數(shù)字重復(fù)幾次丑搔。請找出數(shù)組中任意一個重復(fù)的數(shù)字厦瓢。 例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}低匙，那么對應(yīng)的輸出是第一個重復(fù)的數(shù)字2旷痕。
知識點(diǎn)
數(shù)組
Qiang的思路
遍歷整個數(shù)組，對每個數(shù)字進(jìn)行標(biāo)記顽冶，出現(xiàn)為True欺抗，沒出現(xiàn)為False，當(dāng)遍歷的時候發(fā)現(xiàn)已經(jīng)為True了就找到了重復(fù)的數(shù)字强重，不為True就將其標(biāo)記為True并繼續(xù)遍歷绞呈。
# -*- coding:utf-8 -*-
class Solution:
# 這里要特別注意~找到任意重復(fù)的一個值并賦值到duplication[0]
# 函數(shù)返回True/False
def duplicate(self, numbers, duplication):
# write code here
flag=[]
for _ in range(len(numbers)): flag.append(False)
for i in numbers:
if flag[i]:
duplication[0]=i
return True
flag[i]=True
return False
時間復(fù)雜性分析
該代碼首先需要得到一個全為False的flag數(shù)組贸人，時間復(fù)雜度為O(n)。然后通過遍歷的方式去判斷是否當(dāng)前的數(shù)為重復(fù)出現(xiàn)的數(shù)佃声，時間復(fù)雜度為O(n)艺智。綜上，時間復(fù)雜度為O(n)圾亏。
空間復(fù)雜性分析
該代碼需要一個長度為n的flag數(shù)組十拣，故空間復(fù)雜度為O(n)。
Book中思路
同樣采取遍歷的方式志鹃，在遍歷的同時判斷當(dāng)前元素i是否等于當(dāng)前下標(biāo)（因?yàn)檎麄€數(shù)組長為n夭问，元素大小從0到n-1），如果不相等則將i與下標(biāo)為i的元素進(jìn)行比較曹铃，如果相等則找到了重復(fù)的元素缰趋，如果不相等則交換。如果當(dāng)前元素i等于下標(biāo)則繼續(xù)遍歷陕见。
這種思路可以將元素i放到下標(biāo)為i的位置秘血，這樣就相當(dāng)于做了標(biāo)記。
# -*- coding:utf-8 -*-
class Solution:
# 這里要特別注意~找到任意重復(fù)的一個值并賦值到duplication[0]
# 函數(shù)返回True/False
def duplicate(self, numbers, duplication):
# write code here
i=0
while i<len(numbers):
if i==numbers[i]:
i+=1
continue
if numbers[i]==numbers[numbers[i]]:
duplication[0]=numbers[i]
return True
# numbers[i],numbers[numbers[i]]=numbers[numbers[i]],numbers[i]
# 這種寫法是不對的评甜，numbers[numbers[i]]受到了numbers[i]的影響
a=numbers[i]
numbers[i]=numbers[a]
numbers[a]=a
return False
時間復(fù)雜性分析
對于每個元素灰粮，最多交換兩次就能找到屬于自己的位置，所以總的時間復(fù)雜度為O(n)蜕着。
這個地方我有一些不同意谋竖，作者在書中寫的是每個元素最多交換兩次红柱，但是這兩次實(shí)際上前一次是因?yàn)樯弦粋€元素交換導(dǎo)致的承匣，下一次又是下一個元素兩次交換中的第一次，所以我認(rèn)為每個元素實(shí)際上最多只需要交換一個就能到達(dá)所在的位置锤悄。
空間復(fù)雜性分析
顯然韧骗，這套代碼的時間復(fù)雜度為O(1)。
作者原創(chuàng)零聚，如需轉(zhuǎn)載及其他問題請郵箱聯(lián)系：lwqiang_chn@163.com袍暴。
個人網(wǎng)站：https://www.myqiang.top。
