說(shuō)明：記錄刷劍指offer，使用php與python兩種語(yǔ)言，對(duì)解題思路以及涉及到的基本語(yǔ)法以及知識(shí)點(diǎn)做學(xué)習(xí)記錄。其中對(duì)于每道題目進(jìn)行粗略的分類。
題目來(lái)源
- 分類：數(shù)組
- 數(shù)組中出現(xiàn)重復(fù)的數(shù)字
題目描述
在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)爱致。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的寒随。也不知道每個(gè)數(shù)字重復(fù)幾次糠悯。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 例如妻往，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}互艾，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2。
解題思路（參考劍指offer 第二版）
- 方法一：暴力直接的結(jié)果方法讯泣，雙循環(huán)纫普，計(jì)數(shù)統(tǒng)計(jì)次數(shù)，此中方法時(shí)間復(fù)雜度為 O(n^2)
- 方法二：把輸入的數(shù)組排序，之后從頭到尾掃描排序后的數(shù)組即可昨稼，排序一個(gè)長(zhǎng)度為n的數(shù)組需要O(nlogn)的時(shí)間
- 方法三：哈希表解決节视，從頭到尾順序掃描數(shù)組的每個(gè)數(shù)字，每掃到一個(gè)數(shù)字的時(shí)候假栓，可以使用O(1)的時(shí)間判斷哈希表是否存在該數(shù)字寻行，沒(méi)有加入哈希表，存在即找到了一個(gè)重復(fù)的數(shù)字匾荆。算法復(fù)雜度為O(n),但提高時(shí)間效率是以空間為代價(jià)的拌蜘。
- 方法四：利用數(shù)組數(shù)字的特性，因?yàn)樗械臄?shù)字都在0到n-1之間牙丽，如果數(shù)組中沒(méi)有重復(fù)的元素简卧，則數(shù)組排序后，第i個(gè)位置值即為i烤芦。由于數(shù)組中有重復(fù)的數(shù)字举娩，所以有些位置與此位置的值存在不匹配的現(xiàn)象。
具體思路：重新排這個(gè)數(shù)組拍棕，從頭到尾掃描這個(gè)數(shù)組中的每個(gè)數(shù)字晓铆，當(dāng)掃描到下標(biāo)尾i的數(shù)字時(shí)勺良，首先比較這個(gè)數(shù)字（用m表示）是否等于i绰播。如果i == m，則直接掃描下一個(gè)數(shù)字尚困；如果i != m, 則需要拿此位置的數(shù)m與數(shù)組的第m個(gè)數(shù)字比較蠢箩。如果此數(shù)字與第m個(gè)數(shù)字相等則找到了第一個(gè)重復(fù)的數(shù)字（此數(shù)字在i和m位置都出現(xiàn)了）；如果不想等事甜，就把第i個(gè)位置的數(shù)m與第m個(gè)位置的數(shù)字交換谬泌，把m放在應(yīng)該放的位置上，之后重復(fù)比較逻谦、交換的過(guò)程掌实，直至發(fā)現(xiàn)一個(gè)重復(fù)的數(shù)字。
例如：{2,3,1,0,2,5,3} 邦马，數(shù)組名為nums
i = 0 時(shí) nums[i] = 2 贱鼻， nums[i] != i 交換數(shù)字 nums[i] nums[nums[i]]即交換nums[0] 與 nums[2] ,結(jié)果為[1,3,2,0,2,5,3];
此時(shí)第0個(gè)數(shù)字是1，仍與下標(biāo)本相等滋将，繼續(xù)把它和下標(biāo)為1的數(shù)字交換邻悬，結(jié)果為[3,1,2,0,2,5,3];
第0個(gè)數(shù)字是3，仍與下標(biāo)本相等随闽，繼續(xù)把它和下標(biāo)為3的數(shù)字交換父丰，結(jié)果為[0,1,2,3,2,5,3];
此時(shí)第0個(gè)位置數(shù)與此下標(biāo)相等，接下來(lái)的數(shù)字中掘宪，下標(biāo)1蛾扇，2攘烛，3的3個(gè)數(shù)都與下標(biāo)相等，所以不需要執(zhí)行任何操作镀首，接下來(lái)掃描下標(biāo)為4的數(shù)字2医寿，由于下標(biāo)與其數(shù)值不想等，需要和下標(biāo)為2的數(shù)字比較蘑斧，此時(shí)數(shù)組中下標(biāo)為2的數(shù)字也是2靖秩，因此找到一個(gè)重復(fù)的數(shù)字。
編程實(shí)現(xiàn)
PHP
<?php
運(yùn)行時(shí)間：30ms
占用內(nèi)存：2504k
function duplicate($numbers, &$duplication)
{
//這里要特別注意~找到任意重復(fù)的一個(gè)值并賦值到duplication[0]
//函數(shù)返回True/False
$length = count($numbers);
if (empty($numbers) || $length <= 0):
return false;
foreach ($numbers as $item) {
if ($item < 0 || $item > $length - 1) {
return false;
}
}
for ($i = 0; $i < $length; $i++ ) {
while ($i != $numbers[$i]) {
if($numbers[$i] == $numbers[$numbers[$i]]){
$duplication[0] = $numbers[$i];
return true;
}
$temp = $numbers[$i];
$numbers[$i] = $numbers[$temp];
$numbers[$temp] = $temp;
}
}
}
?>
Python
# -*- coding:utf-8 -*-
class Solution:
def duplicate(self, numbers, duplication):
# write code here
if not numbers or len(numbers) <= 0:
return False
for num in numbers:
count = 0
for item in numbers:
if num == item:
count += 1
if count > 1:
duplication[0] = item
return duplication[0]
break
return False
# 運(yùn)行時(shí)間：29ms
#
# 占用內(nèi)存：5736k
def duplications(self, nums, dups):
if not nums or len(dups) <= 0:
return False
for i in range(len(nums)):
if (nums[i] < 0 ) or (nums[i] > len(nums) - 1):
return False
for i in range(len(nums)):
while i != nums[i]:
if nums[i] == nums[nums[i]]:
dups[0] = nums[i]
return True
temp = nums[i]
nums[i] = nums[temp]
nums[temp] = temp
return False
s = Solution()
print s.duplicate([2,1,3,0,4], [0])
print s.duplications([2,3,1,0,2,5,3], [0])
知識(shí)點(diǎn)總結(jié)
- php引用傳遞參數(shù)
調(diào)用一個(gè)函數(shù)竖瘾，只能有一個(gè)返回值沟突，（除非你返回的是一個(gè)數(shù)組，數(shù)組里就可以包含多個(gè)值捕传，但嚴(yán)格來(lái)說(shuō)惠拭，這也是只能返回一個(gè)值，一個(gè)數(shù)組）庸论。
但你調(diào)用函數(shù)职辅，需要返回二個(gè)值時(shí)，使用引用傳遞就間接達(dá)到這個(gè)目的聂示。
