力扣题目链接:https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/
给你一个整数数组 n u m s nums nums ,该数组具有以下属性:
- n u m s . l e n g t h = = 2 ∗ n nums.length == 2 * n nums.length==2∗n.
- n u m s nums nums 包含 n + 1 n + 1 n+1 个 不同的 元素
- n u m s nums nums 中恰有一个元素重复 n n n 次
找出并返回重复了 n n n 次的那个元素。
示例 1:
输入:nums = [1,2,3,3]
输出:3
示例 2:
输入:nums = [2,1,2,5,3,2]
输出:2
示例 3:
输入:nums = [5,1,5,2,5,3,5,4]
输出:5
提示:
- 2 ≤ n ≤ 5000 2\leq n\leq 5000 2≤n≤5000
- n u m s . l e n g t h = = 2 ∗ n nums.length == 2 * n nums.length==2∗n
- 0 ≤ n u m s [ i ] ≤ 1 0 4 0\leq nums[i]\leq10^4 0≤nums[i]≤104
-
n
u
m
s
nums
nums由
n
+
1
n+1
n+1个不同的元素组成,且其中一个元素恰好重复
n
次
有一个元素出现了 n n n次,其余元素都只出现了 1 1 1次
方法一:排序这让我们很容易想到排序。排序后相同的数字会挨到一起,从前向后遍历数组,如果有相邻的两个数字相同,那么这个数字就是答案。
- 时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
- 空间复杂度 O ( n ) O(n) O(n)
class Solution {
public:
int repeatedNTimes(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; // Fake return:LeetCode编译器必须要求有一个返回值
}
};
方法二:哈希表
我们可以用哈希表记录下每个数出现的次数,如果遇到出现两次的数字就是答案。
- 时间复杂度 O ( n ) O(n) O(n)
- 空间复杂度 O ( n ) O(n) O(n)
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
unordered_set<int> appended; // 记录已经出现过的元素
for (int& t : nums) { // 遍历
if (appended.count(t)) { // 出现过
return t;
}
appended.insert(t);
}
return -1; // Fake return
}
};
方法三:数学
首先我们可以思考:一个数组中有 n n n个相同的数,这些相同的数中,距离最近的两个数的最大距离是多少呢?
答案肯定不会很大吧。实际上确实如此。证明如下:
记 n n n个相同的数为 x x x,假设每两个 x x x之间都间隔了 ≥ 2 \geq2 ≥2个数。那么 n n n个 x x x需要至少 2 × ( n − 1 ) 2\times(n-1) 2×(n−1)个数来间隔。但是非 x x x的数只有 n n n个。只有 n ≥ 2 × ( n − 1 ) n\geq 2\times(n-1) n≥2×(n−1)时上述假设才成立。解得 n ≤ 2 n\leq2 n≤2。
也就是说,只有 n = 2 n=2 n=2时,才有可能满足两个 x x x之间间隔 ≥ 2 \geq2 ≥2( [ x , a , b , x ] [x,a,b,x] [x,a,b,x])
n > 2 n>2 n>2时,必存在两个间距 < 2 <2 <2的相同的 x x x。
因此我们只需要在“相邻两个数、间隔一个数”的条件下,就能找到答案( n = 2 n=2 n=2时除外)
- 时间复杂度 O ( n ) O(n) O(n)
- 空间复杂度 O ( 1 ) O(1) O(1)
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
if (nums.size() == 4) { // n = 2时特判
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 4; j++) {
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
}
// n > 2
for (int i = 0; i < nums.size(); i++) {
if (i + 1 < nums.size() && nums[i + 1] == nums[i]) {
return nums[i];
}
if (i + 2 < nums.size() && nums[i + 2] == nums[i]) {
return nums[i];
}
}
return -1; // Fake return
}
};
方法四:随机选择
这种方法就是无脑随机选取两个下标不同的数,看两个数是否相等。如果不相等继续选择,直到相等为止。
这种方法看似很笨,其实效率很高。因为选择两个数相同的概率是 n 2 n × n − 1 2 n ≈ 1 4 \frac{n}{2n}\times\frac{n-1}{2n}\approx \frac{1}{4} 2nn×2nn−1≈41,平均 4 4 4次随机选择就能找到答案。因此期望时间复杂度为 O ( 1 ) O(1) O(1)。
- 期望时间复杂度 O ( 1 ) O(1) O(1)
- 空间复杂度 O ( 1 ) O(1) O(1)
// 不可以这样写,因为这样可能会选取两个相同的下标
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
srand(time(NULL));
int location;
do {
location = rand() % nums.size();
} while (nums[location] != nums[rand() % nums.size()]);
return nums[location];
}
};
C++正确示范
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
srand(time(NULL));
int loc1, loc2;
do {
loc1 = rand() % nums.size();
loc2 = rand() % nums.size();
} while (nums[loc1] != nums[loc2]);
return nums[loc1];
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/124897591
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)