題目：
在一個(gè)長度為n的數(shù)組里有所有數(shù)字都在0~n-1的范圍內(nèi)，數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，
也不知道每個(gè)數(shù)字重復(fù)了幾次，請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字，例如，如果輸入長度為7的數(shù)組 [ 2, 3, 1, 0, 2, 5, 3 ] ，
那么對(duì)應(yīng)的輸出是重復(fù)的數(shù)字2或者3。
對(duì)原數(shù)組進(jìn)行排序然后順序查找，時(shí)間 O(nlogn) 空間 O(1)
利用哈希表解決，無需修改原數(shù)組，時(shí)間 O(n) 空間 O(n)
交換原數(shù)組中的元素，時(shí)間 O(n) 空間 O(1)
以下是第三種方法的實(shí)現(xiàn)
def
repeat
(
array
)
:
if
not
isinstance
(
array
,
list
)
:
return
-
1
n
=
len
(
array
)
for
i
in
range
(
n
)
:
if
not
isinstance
(
array
[
i
]
,
int
)
:
return
-
1
if
array
[
i
]
<
0
or
array
[
i
]
>=
n
:
return
-
1
for
i
in
range
(
n
)
:
m
=
array
[
i
]
while
(
m
!=
i
)
:
if
m
==
array
[
m
]
:
return
m
;
else
:
array
[
i
]
,
array
[
m
]
=
array
[
m
]
,
array
[
i
]
return
-
1
# 測(cè)試用例
# 長度為 n 的數(shù)組里包含一個(gè)或多個(gè)重復(fù)的數(shù)字
test_case1
=
[
2
,
3
,
1
,
0
,
2
,
5
,
3
]
# 數(shù)組中不含重復(fù)的數(shù)字
test_case2
=
[
2
,
3
,
1
,
5
,
4
,
0
]
# 無效輸入測(cè)試用例
test_case3
=
None
test_case4
=
[
2
,
6
,
1
,
0
]
print
(
"test case1:"
,
repeat
(
test_case1
)
)
print
(
"test case2:"
,
repeat
(
test_case2
)
)
print
(
"test case3:"
,
repeat
(
test_case3
)
)
print
(
"test case4:"
,
repeat
(
test_case4
)
)
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
