亲宝软件园·资讯

展开

Go语言LeetCode题解961在长度2N的数组中找出重复N次元素

刘09k11 人气:0

题目描述

961. 在长度 2N 的数组中找出重复 N 次的元素

给你一个整数数组 nums ,该数组具有以下属性:

找出并返回重复了 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;
    }
};

加载全部内容

相关教程
猜你喜欢
用户评论