【每日一题】【leetcode】8. 数组-数组中重复的数字
【每日一题】【leetcode】8. 数组-数组中重复的数字
aneutron
发布于 2022-08-10 13:59:22
发布于 2022-08-10 13:59:22
代码可运行
运行总次数：0
代码可运行
题目
找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 难易程度：easy
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
限制：
2 <= n <= 100000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
本题解法很多。注意两点：
- 查找：想到随机查找（数组下标、关联容器key）
- 所有数字都在 0～n-1 的范围内：可以利用数据下标
- 找出数组中任意一个重复的数字
解法一
分析
可以在遍历数组的同时对每一个元素做一个标记，这个标记是可以在O(1)时间复杂度获取的，继续遍历数组，并判断元素标记，如果已经存在，则直接返回，否则改变标志。具体流程如下：
- 创建一个
map<int, bool> ret - 遍历数组
nums,如果ret[nums[i]]不存在，则ret[nums[i]] = true；如果ret[nums[i]] = true，则返回nums[i]
tips：步骤1中使用map并不是最优的,也可以使用set。在数组元素重复的比较少的时候可以使用vector。
时间复杂度：O(N) 空间复杂度：O(N)
代码
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
map<int, bool> ret;// 使用map
for (int i = 0; i < nums.size(); i++) {
if (ret.count(nums[i]) == 0) {
ret[nums[i]] = true;
} else {
return nums[i];
}
}
return -1;
}
};class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
vector<bool> ret(nums.size(), false);// 使用vector
for (int i = 0; i < nums.size(); i++) {
if (ret[nums[i]] == false) {
ret[nums[i]] = true;
} else {
return nums[i];
}
}
return -1;
}
};class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
set<int> ret;// 使用set
for (int i = 0; i < nums.size(); i++) {
if (!ret.insert(nums[i]).second) {
return nums[i];
}
}
return -1;
}
};解法二
分析
本题并没限制不能改变原有数组nums，同时强调，所有数字都在 0～n-1 的范围内。因此，可以将元素nums[i]移动到nums[nums[i]]：
- 当
nums[i] == i,说明i位置上的元素已经是i了，不做任何处理，继续遍历 - 当
nums[i] == nums[nums[i]]，说明nums[i]位置的元素已经是nums[i],说明重复了，返回nums[i]即可 - 当上述两个条件都不满足的时候，交换一下
时间复杂度：O(N) 空间复杂度：O(1)
代码
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == i ) {
continue;
} else if (nums[i] == nums[nums[i]]) {
return nums[nums[i]];
} else {
int tmp = nums[i];
nums[i] = nums[nums[i]];
nums[tmp] = tmp;
}
}
return -1;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-02-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
