這兩道題題目基本一樣，只不過一個只需要找到一個，一個需要找到所有的數(shù)字，難度稍稍大了一點，廢話不多說直接上題。
題目一
這道題其實還是比較簡單的，而且解決方法也很多樣，這里我會列舉幾種常用的方法，并講解一種比較巧妙的方法。
核心思想
-
暴力法
既然要找重復(fù)的數(shù)字，那最直接的方法就是遍歷每個元素，然后對每個元素向后繼續(xù)遍歷剩下的元素，找到重復(fù)的直接返回即可。時間復(fù)雜度O(N2) -
集合法
我們可以使用一個集合(或者定義一個大數(shù)組，下標(biāo)對應(yīng)給定數(shù)組元素的值，然后0表示沒有這個數(shù)，1表示出現(xiàn)過這個數(shù)即可)HashSet，然后遍歷數(shù)組向集合中加入元素，如果contains的話返回即可。時間復(fù)雜度O(N)，空間復(fù)雜度O(N) -
排序法
既然要尋找重復(fù)元素，直接將數(shù)組排序，然后找到 nums[i] == nums[i + 1]直接返回即可。時間復(fù)雜度O(nlogn) 不過Java的快排在實際使用時效率可能會優(yōu)于維護(hù)HashSet。
這些就是比較常見而且容易想到的方法，接下來的方法可能不是很容易想到，是在集合法的基礎(chǔ)上進(jìn)行優(yōu)化，由于集合法需要額外的O(N)的空間，可以對此進(jìn)行優(yōu)化。至于優(yōu)化的方法，就是使用題目給的 nums數(shù)組，從而不需要使用額外的空間。因為題目給出了數(shù)組里的數(shù)字都限定在 0 — n - 1之間，那么我們可以讓數(shù)字i 就存放在數(shù)組的 nums[i] 的位置上，詳見代碼。
完整代碼
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]]){
//想要交換的數(shù)組元素重復(fù)
return nums[i];
}
int temp = nums[i];//備份nums[i];
nums[i] = nums[temp];//交換nums[nums[i]] 和nums[i]
nums[temp] = temp;
}
}
return -1;
}
}
對于每一個下標(biāo) i 都判斷他的位置是否放了正確的數(shù)字 i ，是的話直接判斷下一個下標(biāo)，不是的話將nums[i] 交換到正確的位置然后依次循環(huán)，而如果他想要交換的元素已經(jīng)出現(xiàn)過并且在正確位置了，就代表出現(xiàn)了重復(fù)，直接返回即可。時間復(fù)雜度O(N) 雖然使用了兩層循環(huán)，但是依然是每個元素只訪問一次，正確位置或者交換過到了正確位置的會直接跳過。 空間復(fù)雜度O(1) 除了題目給出的nums數(shù)組，沒有使用額外的空間，是一個優(yōu)解。
題目二
核心思路
這道題跟上一題十分相似，但是細(xì)節(jié)上差了不少，這道題的數(shù)組限制元素的范圍在1-n，也就是說還可以按上一題的交換方法，使得1在0處，2在1處……即可；再一個重復(fù)元素只會出現(xiàn)兩次，并且要返回所有的重復(fù)元素，方法同樣可以有多種，暴力、排序、集合都可以解決。不過題干給出一句“你可以不用到任何額外空間并在O(N)時間復(fù)雜度內(nèi)解決這個問題嗎？”，發(fā)現(xiàn)這個要求很苛刻，上邊的三種方法都不能實現(xiàn)，而第一題的方法使用過了就不再贅述，我們嘗試換一種方法，那該怎么解決呢？根據(jù)上一題的思路，我們需要在集合法的基礎(chǔ)上將集合和給定的nums數(shù)組融到一起，以達(dá)到O(N)時間及無額外空間的要求?？梢宰⒁獾筋}干給出的加粗字 兩次 ，兩次就是在引到我們到：-（-1）= 1，也就是說，我們?nèi)匀豢梢杂脭?shù)組的下標(biāo)來代表元素，只不過這次我們不再用值，而是用符號，根據(jù)元素的范圍，數(shù)組元素都是正整數(shù)，那只要對出現(xiàn)過的元素對應(yīng)下標(biāo)的元素符號改為 ‘-’ 就可以不使用額外的空間來解決問題。
完整代碼
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> findDuplicates(int[] nums) {
ArrayList<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
if (nums[Math.abs(nums[i]) - 1] < 0) {
ans.add(Math.abs(nums[i]));
} else {
nums[Math.abs(nums[i]) - 1] *= -1;
}
}
return ans;
}
}
如果數(shù)字nums[i] 出現(xiàn)過，那么它對應(yīng)的下標(biāo)元素 nums[nums[i]]就應(yīng)該小于0，從而找到重復(fù)的元素。須要注意的是，因為當(dāng)前遍歷的nums[i]元素可能在之前被置為 -nums[i] 所以訪問的時候要注意使用絕對值，不然會超出下標(biāo)界限報錯。這種方法還是很巧妙的，當(dāng)然用上一題的交換方法也是可以AC的，看個人選擇即可。
