Go语言LeetCode题解961在长度2N的数组中找出重复N次元素
目录
- 题目描述
- 思路分析
- AC 代码
题目描述
给你一个整数数组 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; } };
以上就是Go语言LeetCode题解961在长度2N的数组中找出重复N次元素的详细内容,更多关于Go题解长度2N数组重复元素的资料请关注我们其它相关文章!
赞 (0)