Go语言LeetCode题解961在长度2N的数组中找出重复N次元素
刘09k11 人气:0题目描述
给你一个整数数组 nums ，该数组具有以下属性：
- nums.length == 2 * n.
- nums 包含 n + 1 个 不同的 元素
- nums 中恰有一个元素重复 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
nums.length == 2 * n
0 <= nums[i] <= 10^4
nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次
思路分析
先来复习一下2n+1：
2n+1个数字中，其中有n+1个数字是相同的，找出这个重复次数最多的数字
同归于尽法，每遍历一个元素，检查手里的元素与之是不是相同 如果相同计数+1，不相同计数-1， 如果手里没有元素，也就是当计数为0的时候，将当前的这个元素拿到手里
现在来看这个题目。2n个元素，要是按照之前那个同归于尽的做法来，最后手里不会有元素存在的，都同归于尽了 那怎么办呢？
既然没有2n+1的场景，那我们就尽量制造出这个情况
比如：[1,2,4,5,3,3,3,3]这个序列
我们就把第一个元素1为要剔除的元素 将原来的数组分成了两部分，[1,2]和 [4,5,3,3,3,3] 对后一部分的序列用同归于尽的做法，是不是就得到结果了！！
当然有人会问，1如果是结果怎么办呢，比如这个序列[1,1,1,1,2,4,5,3] 这样的情况，只需要在剔除1的时候，给1计数就行了，
最后测量1的个数是不是有n个，如果1有n个，那么结果为1，1小于n，那么结果就很明显了。
AC 代码
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
int assumtp_num = A[0],assumtp_num_Count = 1;
int temp_num,Count = 0;
for (int i = 1; i < A.size(); ++i) {
if(A[i]==assumtp_num)
++assumtp_num_Count;
else{
if(A[i]==temp_num)
++Count;
else{
if(Count==0){
Count = 1;
temp_num = A[i];
} else{
--Count;
}
}
}
}
//cout<<assumtp_num_Count<<endl;
return assumtp_num_Count *2==A.size()?assumtp_num:temp_num;
}
};加载全部内容