在一個長度為 n 的陣列里，所有數字都在 0 到 n-1 的范圍內，陣列中某些數字是重復的，但不知道有幾個數字重復，也不知道每個數字重復幾次，請找出陣列中第一個重復的數字，例如，如果輸入長度為 7 的陣列 {2,3,1,0,2,5,3}，那么對應的輸出是第一個重復的數字 2
解法一
利用 HashMap 鍵不重復的特性，可以輕松找出第一個重復的數字
/*
* 回傳描述：
* 如果陣列中有重復的數字，函式回傳true，否則回傳false
* 如果陣列中有重復的數字，把重復的數字放到引數duplication[0]中
*/
import java.util.HashMap;
public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
boolean flag = false;
HashMap<Integer, Object> map = new HashMap<>();
for(int i = 0; i < length; i++) {
if(map.containsKey(numbers[i])) {
duplication[0] = numbers[i];
flag = true;
break;
}
map.put(numbers[i], null);
}
return flag;
}
}
解法二
有一個條件我們沒有用到，就是資料的范圍是 0 ~ n-1，所以我們可以這么做：
- 設定一個指標 i 指向開頭 0
- 對于 arr[i] 進行判斷，如果 arr[i] == i，說明下標為 i 的資料正確的放在了該位置上，讓 i++
- 如果 arr[i] != i，說明沒有正確放在位置上，那么我們就把 arr[i] 放在正確的位置上，也就是交換 arr[i] 和 arr[arr[i]]，交換之后，如果 arr[i] ！= i，繼續交換
- 如果交換的程序中，arr[i] == arr[arr[i]]，說明遇到了重復值，回傳即可
/*
* 回傳描述：
* 如果陣列中有重復的數字，函式回傳true，否則回傳false
* 如果陣列中有重復的數字，把重復的數字放到引數duplication[0]中
*/
public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
for(int i = 0; i < length; i++) {
// 不相等就一直交換
if(i != numbers[i]) {
if(numbers[i] != numbers[numbers[i]]) {
int temp = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i];
numbers[i] = temp;
} else {
duplication[0] = numbers[i];
return true;
}
}
}
return false;
}
}
解法三
還是之前的條件，資料的范圍是 0 ~ n-1，所以可以利用現有陣列設定標志，當一個數字被訪問過后，可以設定對應位上的數 + n，之后再遇到相同的數時，會發現對應位上的數已經大于等于n了，那么直接回傳這個數即可
/*
* 回傳描述：
* 如果陣列中有重復的數字，函式回傳true，否則回傳false
* 如果陣列中有重復的數字，把重復的數字放到引數duplication[0]中
*/
public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers == null || numbers.length == 0) {
duplication[0] = -1;
return false;
}
for(int i = 0; i < numbers.length; i++) {
// 得到當前正在遍歷的數
int index = numbers[i];
// index 有可能已被改變，為了找到正確的對應陣列位置，必須減去length
if(index >= length) {
index -= length;
}
// 對應位置如果大于length，則為重復數字
if(numbers[index] >= length) {
duplication[0] = index;
return true;
}
numbers[index] += length;
}
return false;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/231835.html
標籤：其他
上一篇：最長上升子序列（實驗回顧）
下一篇：構建乘積陣列