Go語言LeetCode題解961在長度2N的數(shù)組中找出重復(fù)N次元素

更新時(shí)間：2022年12月28日 11:45:18 作者：劉09k11

這篇文章主要為大家介紹了Go語言LeetCode題解961在長度2N的數(shù)組中找出重復(fù)N次元素示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

961. 在長度 2N 的數(shù)組中找出重復(fù) N 次的元素

給你一個(gè)整數(shù)數(shù)組 nums ，該數(shù)組具有以下屬性：

nums.length == 2 * n.
nums 包含 n + 1 個(gè) 不同的元素
nums 中恰有一個(gè)元素重復(fù) n 次

找出并返回重復(fù)了 n 次的那個(gè)元素。

示例 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 個(gè) 不同的元素組成，且其中一個(gè)元素恰好重復(fù) n 次

思路分析

先來復(fù)習(xí)一下2n+1：

2n+1個(gè)數(shù)字中，其中有n+1個(gè)數(shù)字是相同的，找出這個(gè)重復(fù)次數(shù)最多的數(shù)字

同歸于盡法，每遍歷一個(gè)元素，檢查手里的元素與之是不是相同如果相同計(jì)數(shù)+1，不相同計(jì)數(shù)-1，如果手里沒有元素，也就是當(dāng)計(jì)數(shù)為0的時(shí)候，將當(dāng)前的這個(gè)元素拿到手里

現(xiàn)在來看這個(gè)題目。2n個(gè)元素，要是按照之前那個(gè)同歸于盡的做法來，最后手里不會有元素存在的，都同歸于盡了那怎么辦呢？

既然沒有2n+1的場景，那我們就盡量制造出這個(gè)情況

比如：[1,2,4,5,3,3,3,3]這個(gè)序列

我們就把第一個(gè)元素1為要剔除的元素將原來的數(shù)組分成了兩部分，[1,2]和 [4,5,3,3,3,3] 對后一部分的序列用同歸于盡的做法，是不是就得到結(jié)果了?。?/p>

當(dāng)然有人會問，1如果是結(jié)果怎么辦呢，比如這個(gè)序列[1,1,1,1,2,4,5,3] 這樣的情況，只需要在剔除1的時(shí)候，給1計(jì)數(shù)就行了，

最后測量1的個(gè)數(shù)是不是有n個(gè)，如果1有n個(gè)，那么結(jié)果為1，1小于n，那么結(jié)果就很明顯了。

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的數(shù)組中找出重復(fù)N次元素的詳細(xì)內(nèi)容，更多關(guān)于Go題解長度2N數(shù)組重復(fù)元素的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: