題目：
在一個長度為n的數組里有所有數字都在0~n-1的范圍內，數組中某些數字是重復的，但不知道有幾個數字重復了，
也不知道每個數字重復了幾次，請找出數組中任意一個重復的數字，例如，如果輸入長度為7的數組 [ 2, 3, 1, 0, 2, 5, 3 ] ，
那么對應的輸出是重復的數字2或者3。
對原數組進行排序然后順序查找，時間 O(nlogn) 空間 O(1)
利用哈希表解決，無需修改原數組，時間 O(n) 空間 O(n)
交換原數組中的元素，時間 O(n) 空間 O(1)
以下是第三種方法的實現
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
# 測試用例
# 長度為 n 的數組里包含一個或多個重復的數字
test_case1
=
[
2
,
3
,
1
,
0
,
2
,
5
,
3
]
# 數組中不含重復的數字
test_case2
=
[
2
,
3
,
1
,
5
,
4
,
0
]
# 無效輸入測試用例
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
)
)
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
