Go語(yǔ)言LeetCode題解961在長(zhǎng)度2N的數(shù)組中找出重復(fù)N次元素
題目描述
961. 在長(zhǎng)度 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 次
思路分析
先來(lái)復(fù)習(xí)一下2n+1：
2n+1個(gè)數(shù)字中，其中有n+1個(gè)數(shù)字是相同的，找出這個(gè)重復(fù)次數(shù)最多的數(shù)字
同歸于盡法，每遍歷一個(gè)元素，檢查手里的元素與之是不是相同 如果相同計(jì)數(shù)+1，不相同計(jì)數(shù)-1， 如果手里沒(méi)有元素，也就是當(dāng)計(jì)數(shù)為0的時(shí)候，將當(dāng)前的這個(gè)元素拿到手里
現(xiàn)在來(lái)看這個(gè)題目。2n個(gè)元素，要是按照之前那個(gè)同歸于盡的做法來(lái)，最后手里不會(huì)有元素存在的，都同歸于盡了 那怎么辦呢？
既然沒(méi)有2n+1的場(chǎng)景，那我們就盡量制造出這個(gè)情況
比如：[1,2,4,5,3,3,3,3]這個(gè)序列
我們就把第一個(gè)元素1為要剔除的元素 將原來(lái)的數(shù)組分成了兩部分，[1,2]和 [4,5,3,3,3,3] 對(duì)后一部分的序列用同歸于盡的做法，是不是就得到結(jié)果了?。?/p>
當(dāng)然有人會(huì)問(wèn)，1如果是結(jié)果怎么辦呢，比如這個(gè)序列[1,1,1,1,2,4,5,3] 這樣的情況，只需要在剔除1的時(shí)候，給1計(jì)數(shù)就行了，
最后測(cè)量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語(yǔ)言LeetCode題解961在長(zhǎng)度2N的數(shù)組中找出重復(fù)N次元素的詳細(xì)內(nèi)容，更多關(guān)于Go題解長(zhǎng)度2N數(shù)組重復(fù)元素的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Golang Gin框架實(shí)現(xiàn)文件下載功能的示例代碼
本文主要介紹了Golang Gin框架實(shí)現(xiàn)文件下載功能的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
這篇文章主要為大家介紹了goquery 入門(安裝使用)教程示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-10-10
Golang中urlencode與urldecode編碼解碼詳解
這篇文章主要給大家介紹了關(guān)于Golang中urlencode與urldecode編碼解碼的相關(guān)資料,在Go語(yǔ)言中轉(zhuǎn)碼操作非常方便,可以使用內(nèi)置的encoding包來(lái)快速完成轉(zhuǎn)碼操作,Go語(yǔ)言中的encoding包提供了許多常用的編碼解碼方式,需要的朋友可以參考下2023-09-09
GoLang channel底層代碼實(shí)現(xiàn)詳解
Channel和goroutine的結(jié)合是Go并發(fā)編程的大殺器。而Channel的實(shí)際應(yīng)用也經(jīng)常讓人眼前一亮，通過(guò)與select，cancel，timer等結(jié)合，它能實(shí)現(xiàn)各種各樣的功能。接下來(lái)，我們就要梳理一下GoLang channel底層代碼實(shí)現(xiàn)2022-10-10
這篇文章主要介紹了1行Go代碼實(shí)現(xiàn)反向代理的示例，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-08-08
golang?xorm?自定義日志記錄器之使用zap實(shí)現(xiàn)日志輸出、切割日志(最新)
這篇文章主要介紹了golang?xorm?自定義日志記錄器，使用zap實(shí)現(xiàn)日志輸出、切割日志,包括連接postgresql數(shù)據(jù)庫(kù)的操作方法及?zap日志工具?，本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-10-10
Go語(yǔ)言提供了幾種不同的作用域類型,使得開(kāi)發(fā)者可以靈活地控制變量的可見(jiàn)范圍和生命周期,本章節(jié)將詳細(xì)概述Go語(yǔ)言中變量的各種作用域,幫助讀者更好地理解和應(yīng)用這些概念,需要的朋友可以參考下2024-06-06
golang服務(wù)報(bào)錯(cuò):?write:?broken?pipe的解決方案
在開(kāi)發(fā)在線客服系統(tǒng)的時(shí)候,看到日志里有一些錯(cuò)誤信息,下面這篇文章主要給大家介紹了關(guān)于golang服務(wù)報(bào)錯(cuò):?write:?broken?pipe的解決方案,需要的朋友可以參考下2022-09-09
一文詳解Golang?定時(shí)任務(wù)庫(kù)?gron?設(shè)計(jì)和原理
這篇文章主要介紹了一文詳解Golang?定時(shí)任務(wù)庫(kù)?gron?設(shè)計(jì)和原理，gron是一個(gè)比較小巧、靈活的定時(shí)任務(wù)庫(kù)，可以執(zhí)行定時(shí)的、周期性的任務(wù)。gron提供簡(jiǎn)潔的、并發(fā)安全的接口2022-08-08
使用client-go工具調(diào)用kubernetes API接口的教程詳解(v1.17版本)
這篇文章主要介紹了使用client-go工具調(diào)kubernetes API接口(v1.17版本),本文通過(guò)圖文實(shí)例相結(jié)合給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-08-08