數(shù)組中重復(fù)的數(shù)字
問題描述：
找出數(shù)組中重復(fù)的數(shù)字
在一個(gè)長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字
解題思路
字典法
- 使用
HashSet或者 數(shù)組來記錄已遍歷的數(shù)字，如果找到重復(fù)的數(shù)字，則返回 - 時(shí)間復(fù)雜度：
O(n)，空間復(fù)雜度：O(n)，需要額外空間
class Solution {
public int findRepeatNumber(int[] nums) {
// hashSet
if (nums == null || nums.length == 0)
return -1;
int n = nums.length, ans = -1;
int[] count = new int[n];
for (int num: nums) {
if (count[num] != 0) {
ans = num;
break;
}
count[num]++;
}
return ans;
// int[]
if (nums == null || nums.length == 0)
return -1;
int ans = -1;
Set<Integer> set = new HashSet<>();
for (int num: nums) {
if (!set.add(num)) {
ans = num;
break;
}
set.add(num);
}
return ans;
}
}
排序法
- 先排序，然后遍歷數(shù)組，如果相鄰元素相等，則返回
- 時(shí)間復(fù)雜度：
O(nlogn)，空間復(fù)雜度：O(1)，不需要額外空間，修改輸入數(shù)組
class Solution {
public int findRepeatNumber(int[] nums) {
// 排序
if (nums == null || nums.length == 0)
return -1;
int n = nums.length, ans = -1;
Arrays.sort(nums);
for (int i = 0; i < n - 1; ++i) {
if (nums[i] == nums[i + 1]) {
ans = nums[i];
break;
}
}
return ans;
}
}
置換法
- 置換法，值為
x的元素，置換到數(shù)組索引為x的位置。如果當(dāng)前元素值等于索引值，則繼續(xù)進(jìn)行遍歷，如果不相等，則將nums[x]置換到正確的位置上，即nums[nums[x]]，如果在這個(gè)過程中，數(shù)組nums[x]索引下的值已經(jīng)為nums[nums[x]]，則說明nums[x]重復(fù)，返回即可 - 時(shí)間復(fù)雜度：
O(n)，空間復(fù)雜度：O(1)，不需要額外空間，修改輸入數(shù)組。雖然for循環(huán)里面套了while，但是每一個(gè)數(shù)來到它應(yīng)該在的位置以后，位置就不會(huì)再變化。這里用到的是均攤復(fù)雜度分析的方法：如果在某一個(gè)位置while循環(huán)體執(zhí)行的次數(shù)較多，那么一定在后面的幾個(gè)位置，根本不會(huì)執(zhí)行while循環(huán)體內(nèi)的代碼，也就是說最壞的情況不會(huì)一直出現(xiàn)。也就是說最壞復(fù)雜度的情況不會(huì)一直出現(xiàn)。
class Solution {
public int findRepeatNumber(int[] nums) {
// 交換
if (nums == null || nums.length == 0)
return -1;
int n = nums.length, ans = -1;
for (int i = 0; i < n; ++i) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return ans;
}
}
拓展
與上面題類似，但因?yàn)閿?shù)組長度和數(shù)組元素限制的特點(diǎn)，解題思路不同
- 二分法
- 快慢指針法
