【剑指Offer】面试题03. 数组中重复的数字
2024-08-28 03:33:42
题目
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
限制:
2 <= n <= 100000
思路一:哈希表
初始化哈希表大小为数组元素大小,初始值为-1(因为数组中所有元素大于0)。
遍历数组每个数字n,如果哈希值为0,表示该数字已经存在,直接返回;否则,更新数字n对应位置哈希值为0表示已经存在。
代码
时间复杂度:O(n)
空间复杂度:O(n)
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
vector<int> hash(nums.size(), -1);
for (auto n : nums) {
if (hash[n] == 0) return n;
++hash[n];
}
return -1;
}
};
思路二:排序后查找
排序后,如果存在相邻两个数字相等则返回。
代码
时间复杂度:O(nlogn)
空间复杂度:O(1)
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] == nums[i - 1]) return nums[i];
}
return -1;
}
};
思路三:交换位置
对每个数组下标位置 i,判断是否等于nums[i]
- 如果下标位置 i 不等于 nums[i],则nums[i]实际应该放在nums[nums[i]]位置上
- 如果nums[i] 等于 nums[nums[i]],则找到重复元素;
- 否则,交换nums[i] 和 nums[nums[i]],即将nums[i]放在了正确的位置。
- 如果相等,则判断下一个位置。
代码
时间复杂度:O(n)
空间复杂度:O(1)
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
while (nums[i] != i) {
if (nums[nums[i]] == nums[i]) return nums[i];
swap(nums[i], nums[nums[i]]);
}
}
return -1;
}
};
最新文章
- 【CoreAnimation】1 到 5
- sha256 C语言
- git服务器搭建
- JSTL Tag学习笔记(一)之<;c: />;
- jQuery将字符串转换成json
- JavaScript中常谈的对象
- 【19】设计class犹如设计type
- QT5-控件-QProgressBar-进度条-用来做下载进度,文件读取进度还不错
- Ext Radio 取消选中
- Mysql 多表查询
- qsort()函数(C)
- Go 语言范围(Range)
- 深度学习中Embedding的理解
- python练习题-day25
- 201771010134杨其菊《面向对象程序设计(java)》第十三周学习总结
- python基础四-文件读取
- JS中----this的指向和如何修改this的指向
- 正则表达式(特殊字符)/Xpath语法/CSS选择器
- python函数的万能参数
- denyhost安装脚本