找出數(shù)組中重復(fù)的數(shù)字己沛。
在一個(gè)長(zhǎng)度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)竹祷。數(shù)組中某些數(shù)字是重復(fù)的疆拘，但不知道有幾個(gè)數(shù)字重復(fù)了寝并，也不知道每個(gè)數(shù)字重復(fù)了幾次箫措。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。
示例 1：
輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3
限制：
2 <= n <= 100000
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
解題思路
這道題本來(lái)不想寫(xiě)了衬潦，因?yàn)橛X(jué)得過(guò)于簡(jiǎn)單斤蔓，樓主的基本思路就是直接遍歷一遍，放在一個(gè)collection集合類(lèi)的set里面镀岛，如果有重復(fù)就可以返回了弦牡，沒(méi)有就放進(jìn)去。結(jié)果寫(xiě)完了之后看了一下時(shí)間和空間的排名漂羊，不是很高啊驾锰，趕緊去看看大牛的解法，發(fā)現(xiàn)了一種很有意思的解題思路拨与。
- 利用Set 查重 - 簡(jiǎn)單
class Solution {
public int findRepeatNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
int repeatNum = -1;
for(int i= 0; i< nums.length;i++){
if(set.contains(nums[i])){
repeatNum = nums[i];
break;
}
set.add(nums[i]);
}
return repeatNum;
}
}
- 注意審題稻据，沒(méi)有重復(fù)的話則說(shuō)明在i位置上的數(shù)字應(yīng)該就等于i，利用這個(gè)特點(diǎn)可以把nums[i]的數(shù)字m換到nums[m]的位置买喧，如果該位置上已經(jīng)是m了捻悯，則表示有重復(fù)的數(shù)字，否則就置換淤毛。高手今缚！
class Solution {
public int findRepeatNumber(int[] nums) {
for(int i= 0; i< nums.length;i++){
while(nums[i]!=i){
if(nums[i] == nums[nums[i]])
return nums[i];
int tmp = nums[i];
nums[i] = nums[tmp];
nums[tmp] = tmp;
}
}
return -1;
}
}
