剑指offer03 数组中重复的数字
题目描述
找出数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
限制:2 <= n <= 100000
方法一——排序
先把输入的数组排序,然后从头到尾扫描排序后的数组就可以了
时间复杂度O(NlogN)
空间复杂度O(logN)
#include <algorithm>
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n = nums.size();
for(int i = 1;i < n;++i){
if(nums[i] == nums[i-1])
return nums[i];
}return 0;
}
};
方法二——bool数组实现哈希
由于限制了2 <= n <= 100000,我们只需要申请大小为100000的布尔数组,初始化全为false标记数组中的元素出现与否,若第一次出现则置为true,第二次出现则直接输出
时间复杂度O(N)
空间复杂度O(N)
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int n = nums.size();
bool flag[100000] = {false};
for(int i = 0;i < n;++i){
if(flag[nums[i]])
return nums[i];
flag[nums[i]] = true;
}return 0;
}
};
方法三——根据下标定位
注意到数组中的数字都在0~n-1的范围内,如果这个数组中没有重复的数字,那么当数组排序之后数字i将出现在下标为i的位置。由于数组中有重复的数字,那么有些位置就可能存在多个数字。
算法描述
从头到尾依次扫描数组,当扫描到下标为i的数字时,
首先比较这个数字(记为m)是否等于i,
若是,说明数字已在对应位置上了,则接着扫描下一个数字
否则,看数组第m个数字
如果数组第m个数字已经是m的话,说明已经找到重复的元素了
否则,交换数组第i个数字和第m个数字,让m排到属于它的位置
时间复杂度O(N)(遍历和交换均为O(N))
空间复杂度O(1)
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int n = nums.size();
int tmp;
for(int i = 0;i < n;++i){
while(nums[i] != i){
tmp = nums[i];
if(nums[tmp] == tmp)
return tmp;
nums[i] = nums[tmp];
nums[tmp] = tmp;
}
}return 0;
}
};