題目描述
長度為n的數(shù)組nums里的所有數(shù)字都在0~n-1的范圍內(nèi),數(shù)組中某些數(shù)字是重復(fù)的,但不知道有幾個(gè)數(shù)字重復(fù)了,也不知道每個(gè)數(shù)字重復(fù)了幾次,請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)數(shù)字返回涵卵。例如:
輸入:[2,3,1,0,2,5,3]
輸出:2或3
解題思路
1.遍歷法
先定義一個(gè)集合set,從頭開始遍歷數(shù)組中的元素荒叼,每遍歷一個(gè)元素就將該元素插入到定義的集合中轿偎,由于集合中的元素不能有重復(fù),因此當(dāng)插入集合失敗時(shí)被廓,這個(gè)插入失敗的元素就是我們要找的重復(fù)數(shù)字坏晦。C++代碼實(shí)現(xiàn)如下:
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
// 定義一個(gè)集合s
set<int> s;
// 保存insert函數(shù)的返回值,集合插入失敗時(shí)p.second 為bool值false
pair<set<int>::iterator, bool> p;
// 遍歷數(shù)組中的元素
for(int i=0; i<nums.size(); i++){
p = s.insert(nums[i]);
if(!p.second)
return nums[i];
}
// 沒有重復(fù)元素時(shí)返回 -1
return -1;
}
};
2.下標(biāo)定位法
n個(gè)數(shù)字都在0~n-1范圍內(nèi),如果沒有重復(fù)的數(shù)字昆婿,并且數(shù)組是有序的球碉,排好序后數(shù)字m應(yīng)該剛好在下標(biāo)m的位置上。從頭到尾掃描數(shù)組仓蛆,當(dāng)掃描到下標(biāo)為i的數(shù)字時(shí)睁冬,首先比較這個(gè)數(shù)字m是否等于下標(biāo)i,如果等于就繼續(xù)掃描下一個(gè)數(shù)字看疙,如果不等于豆拨,就讓它和第m個(gè)數(shù)字進(jìn)行比較,如果它和第m個(gè)數(shù)字相等能庆,那么出現(xiàn)了重復(fù)直接返回這個(gè)數(shù)字施禾,如果不相等,則將它和第m個(gè)數(shù)字進(jìn)行交換搁胆,即把m放到第m個(gè)位置上弥搞。重復(fù)這個(gè)過程,直到出現(xiàn)一個(gè)重復(fù)的數(shù)字渠旁。C++代碼實(shí)現(xiàn)如下:
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
for(int i=0; i<nums.size(); i++){
//下標(biāo)為i的位置上的元素nums[i]不是i時(shí)和下標(biāo)為nums[i]位置的元素做比較
while(nums[i] != i){
// 下標(biāo)為nums[i]位置的元素也為nums[i]時(shí)拓巧,出現(xiàn)重復(fù)數(shù)字
if(nums[nums[i]] == nums[i])
return nums[i];
else{ // 下標(biāo)為nums[i]位置的元素不為nums[i]時(shí),將它和下標(biāo)為i位置的元素做交換
int temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
}
}
} //沒有重復(fù)數(shù)字時(shí)一死,返回-1
return -1;
}
};