尋找重復數字
大致有兩種不同版本：
1
給定一個包含 n + 1 個整數的陣列 nums ，其數字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數，
假設 nums 只有 一個重復的整數 ，找出 這個重復的數 ，
2
找出陣列中重復的數字，
在一個長度為 n 的陣列 nums 里的所有數字都在 0～n-1 的范圍內，陣列中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次，請找出陣列中任意一個重復的數字，
示例 1：
輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3
限制：
2 <= n <= 100000
總結
對于1 與 2 通用解法為
1、采用hashSet排重 時間復雜度On 空間復雜度On
2、采用排序演算法 時間復雜度Onlogn 空間復雜度O1
對于版本1 由于特殊的數字設定 此處有兩種解決方法：
//將數字想象成一個個鏈表節點：將問題轉換為：尋找有環串列的起始節點
public int findDuplicate(int[] nums) {
//[0],[1,2,3,1],[1,1,1,1],[]
int slow = nums[0];
int fast = nums[nums[0]];
while (slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int find = 0;
while (find != slow){
find = nums[find];
slow = nums[slow];
}
return find;
}
//halfrost巧解 只適用于1 - n的情況
public int findDuplicate(int[] nums) {
for (int i = 0; i < nums.length;i++){
int var = Math.abs(nums[i]);
if (nums[var - 1] < 0 ) return var;
nums[var - 1] *= -1;
}
return -1;
}
對于版本2 此處可使用版本1-1 變體 將數字同同步+1 轉換 也可使用如下需要修改陣列的方法
public int findRepeatNumber(int[] nums) {
//[0],[0,1,2,0],[1,1,1,1],[]
for (int i = 0; i < nums.length;){
if (nums[i] == i){
i++;
continue;
}
else if (nums[i] == nums[nums[i]]){
return nums[i];
}else{
exchange(nums, i, nums[i]);
}
}
return -1;
}
public void exchange(int[] nums, int posa, int posb){
int temp = nums[posa];
nums[posa] = nums[posb];
nums[posb] = temp;
}
總結
1、首先確定要求 遵循如下幾個原則
1、能否對入參進行修改？
2、有無時間、空間復雜度要求？
3、需要考慮的特殊情況， 邊界條件有哪些？
2、完成1后 先撰寫測驗用例 盡量能覆寫以上幾種情況
撰寫完成代碼后需要對已撰寫的測驗用例逐一進行口算測驗
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/277291.html
標籤：其他