氵题一道啦~,直接来吧!!!
题目内容
给定一个长度为 $n$ 的整数数组 nums
,数组中所有的数字都在 $0∼n−1$ 的范围内。
数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
注意:如果某些数字不在 $0∼n−1$ 的范围内,或数组中不包含重复数字,则返回 $-1$;
思路
先判断不符合题目要求的错误,如长度 $n=0$ 或某些数字不在 $0~n-1$ 范围内;
接着,便有两个选择,一个选择十分朴素,也很快能想到,那就是用 桶 记录每个数字出现过的次数,
还有一种选择是将数组 $sort()$ 一遍,那么相同的数字将会 靠在一起 ,依序比较 相邻元素 的值就可以了。
最后如果实在没有找到,返回 $-1$ 。
算法一
//使用桶记录元素出现次数
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
if (nums.size() == 0) return -1; //若长度为0则返回-1
int bucket[nums.size()] = {0}; //定义一个空桶
for (int i = 0; i < nums.size(); i ++)
if (nums[i] < 0 || nums[i] > nums.size() - 1) return -1; //若不在规定范围内则返回-1
else bucket[nums[i]] ++; //记录这个数又出现了一次
for (int i = 0; i < nums.size(); i ++) //i遍历所有可能出现的数
if (bucket[i] > 1) //若i不止出现一次
return i; //返回重复的数
return -1; //实在找不到就返回-1
}
};
算法二
//利用排序的特点比较相邻元素
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n = nums.size();
if (n == 0) return -1; //若长度为0则返回-1
sort(nums.begin(), nums.end()); //排序
if (nums[0] < 0 || nums[n - 1] > n - 1) return -1;
//通过两个边界就可以判断整个数组有没有在规定范围内了
for (int i = 0; i < n - 1; i ++) //i在n-1停止,那么i+1正好在i停止
if (nums[i] == nums[i + 1]) //若相邻两个元素相等
return nums[i]; //则返回相等的元素的值
return -1; //实在找不到就返回-1
}
};