剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组nums里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入: [2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
限制:
2 <= n <= 100000
思想及代码
原地哈希:nums[i]去到索引为k = num[i]的位置
法一:
1. 让nums[i]作为值为k = num[i]的索引
2. 如果num[i]为负,表示这不是由重复引起,则还原
3. 如果num[k]为负由重复引起,则输出索引k,即为重复的数
4. 修改k位置内容nums[k]为负数,即num[k] -= n
Code:
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int len = nums.size();
for(int i=0;i<len;i++){
int k = nums[i];
if(k<0) k+=len; //还原
if(nums[k] < 0) return k; //若以k为下标元素仍为负,则说明k重复了两次,返回k
nums[k] -= len; //标为负数
}
return -1; //没找到
}
};
法二:
1. 先按大小递增排序
2.如果nums[i] == nums[i+1],则nums[i]重复,返回即可
Code:
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
if(nums[i] == nums[i+1]) return nums[i];
}
return -1;
}
};