剑指 Offer（第2版）面试题 3：数组中重复的数字
剑指 Offer（第2版）面试题 3：数组中重复的数字题目一：13. 找出数组中重复的数字解法一：排序+遍历解法二：哈希解法三：遍历
题目二：14. 不修改数组找出重复的数字解法一：二分查找
剑指 Offer（第2版）面试题 3：数组中重复的数字
题目一：13. 找出数组中重复的数字
链接：13. 找出数组中重复的数字
解法一：排序+遍历
对数组进行排序之后，重复的数字必然相邻。遍历一次数组，查找即可，
代码：
class Solution
{
public:
int duplicateInArray(vector
{
if (nums.empty())
return -1;
int n = nums.size();
for (const int &num : nums)
if (num < 0 || num > n - 1)
return -1;
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 1; i++)
if (nums[i] == nums[i + 1])
return nums[i];
return -1;
}
};
时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。
空间复杂度：O(1)。
解法二：哈希
代码：
class Solution
{
public:
int duplicateInArray(vector
{
if (nums.empty())
return -1;
int n = nums.size();
for (const int &num : nums)
if (num < 0 || num > n - 1)
return -1;
unordered_set
for(const int &num:nums)
{
if(us.count(num))
return num;
us.insert(num);
}
return -1;
}
};
时间复杂度：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。
解法三：遍历
首先遍历一遍数组，如果存在某个数不在 0 到 n-1 的范围内，则返回 -1。
下面的算法的主要思想是把每个数放到对应的位置上，即让 nums[i] = i。
从前往后遍历数组中的所有数，假设当前遍历到的数是 nums[i] = x，那么：
如果 x != i && nums[x] == x，则说明 x 出现了多次，直接返回 x；如果 nums[x] != x，那我们就把 x 交换到正确的位置上，即 swap(nums[x], nums[i])，交换完之后如果还是 nums[i] != i，则重复进行该操作。由于每次交换都会将一个数放在正确的位置上，所以 swap 操作最多会进行 n 次，不会发生死循环。
循环结束后，如果没有找到任何重复的数，则返回 -1。
代码：
class Solution
{
public:
int duplicateInArray(vector
{
if (nums.empty())
return -1;
int n = nums.size();
for (const int &num : nums)
if (num < 0 || num > n - 1)
return -1;
for (int i = 0; i < n; i++)
{
while (nums[i] != i)
{
if (nums[i] == nums[nums[i]])
return nums[i];
swap(nums[i], nums[nums[i]]);
}
}
return -1;
}
};
时间复杂度：O(n)，其中 n 是数组 nums 的长度。每次 swap 操作都会将一个数放在正确的位置上，最后一次 swap 会将两个数同时放到正确位置上，一共只有 n 个数和 n 个位置，所以 swap 最多会进行 n-1 次。
空间复杂度：O(1)。
题目二：14. 不修改数组找出重复的数字
链接：14. 不修改数组找出重复的数字
解法一：二分查找
抽屉原理：n+1 个苹果放在 n 个抽屉里，那么至少有一个抽屉中会放两个苹果。
用在这个题目中就是，一共有 n+1 个数，每个数的取值范围是1到n，所以至少会有一个数出现两次。
然后我们采用分治的思想，将每个数的取值的区间 [1, n] 划分成 [1, n/2] 和 [n/2+1, n] 两个子区间，然后分别统计两个区间中数的个数。
注意这里的区间是指数的取值范围，而不是数组下标。
划分之后，左右两个区间里一定至少存在一个区间，区间中数的个数大于区间长度。 这个可以用反证法来说明：如果两个区间中数的个数都小于等于区间长度，那么整个区间中数的个数就小于等于 n，和有 n+1 个数矛盾。
因此我们可以把问题划归到左右两个子区间中的一个，而且由于区间中数的个数大于区间长度，根据抽屉原理，在这个子区间中一定存在某个数出现了 2 次。
依次类推，每次我们可以把区间长度缩小一半，直到区间长度为1时，我们就找到了答案。
代码：
class Solution
{
public:
int duplicateInArray(vector
{
// 特判
if (nums.empty())
return -1;
int n = nums.size();
int start = 1, end = n - 1;
while (start <= end)
{
int mid = (end - start) / 2 + start;
int count = countRange(nums, start, mid);
if (start == end)
{
if (count > 1)
return start;
else
break;
}
if (count > (mid - start + 1))
end = mid;
else
start = mid + 1;
}
}
// 辅函数 - 统计数组 nums 中范围在 [start, end] 内的元素个数
int countRange(vector
{
if (nums.empty())
return 0;
int count = 0;
for (const int num : nums)
if (num >= start && num <= end)
count++;
return count;
}
};
时间复杂度：O(nlogn)。每次会将区间长度缩小一半，一共会缩小 O(logn) 次，每次统计两个子区间中的数时需要遍历整个数组，时间复杂度是 O(n)，所以总时间复杂度是 O(nlogn)。
空间复杂度：O(1)。
文章链接
发表评论