主頁 > 後端開發 > 【Warrior刷題筆記】力扣169. 多數元素 【排序 || 哈希 || 隨機演算法 || 摩爾投票法】詳細注釋 不斷優化 極致壓榨

【Warrior刷題筆記】力扣169. 多數元素 【排序 || 哈希 || 隨機演算法 || 摩爾投票法】詳細注釋 不斷優化 極致壓榨

2022-01-06 06:29:25 後端開發

題目

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/majority-element/
注意,該題在LC中被標注為easy,所以我們更多應該關注的是文章中不斷優化的思路和方法,很多時候面試考察的,就是與面試官一起做題并把時間復雜度和空間復雜度壓榨到極致的程序中你所表現出來的能力,

1.描述

給定一個大小為 n 的陣列,找到其中的多數元素,多數元素是指在陣列中出現次數大于 ?n/2?的元素,
你可以假設陣列是非空的,并且給定的陣列總是存在多數元素,

2.示例

  • 示例 1:
	輸入:[3,2,3]
	輸出:3
  • 示例 2:
	輸入:[2,2,1,1,1,2,2]
	輸出:2

解法一 排序

解題思路

很快啊,啪的一下我們想到,由于多數元素是指在陣列中出現次數 大于 ?n/2? 的元素,那么將陣列排序后,即便該元素是最小元素或是最大元素,其在陣列中的覆寫范圍也超過了陣列中點(從左到右超過或是從右到左超過),于是得到演算法:

演算法

1.將陣列排序;
2.回傳陣列中點元素nums[nums.size()/2].

代碼

1 class Solution {
2 public:
3     int majorityElement(vector<int>& nums) {
4         sort(nums.begin(), nums.end());//對陣列進行排序
5         return nums[nums.size()/2];//回傳陣列中點元素
6     }
7 };

 

復雜度分析

時間復雜度: O(mlogm),m為陣列元素數,主要是排序的時間消耗,
空間復雜度: O(logm),主要是系統sort函式需要的堆疊空間消耗,

解法二 哈希

解題思路

這時候,面試官說,你這解法一的時間復雜度很大啊,你能優化一下嗎,稍加思索,我們想到,如果考慮使用哈希表空間換時間,則可以降低時間復雜度,我們可以使用哈希表存盤陣列中元素出現的次數,當某個元素的出現次數超過一半時,回傳該元素,于是得到演算法:

演算法

1.初始化存盤陣列元素及其出現次數的哈希表map1,鍵為元素值,值為該元素在陣列中的出現次數;
2.遍歷陣列元素,將被遍歷陣列元素的哈希值加一;
3.若該元素在陣列中的出現次數超過陣列元素數的一半,回傳該元素,

代碼

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         unordered_map<int, int> map1;//存盤陣列元素值及出現次數的哈希表
 5         for(int i = 0; i < nums.size(); i++)//遍歷陣列元素
 6         {
 7             map1[nums[i]]++;//該元素出現次數加一
 8             if(map1[nums[i]] > nums.size()/2)//若該元素出現此處超過一半
 9             {
10                 return nums[i];//回傳該元素
11             }
12         }
13         return 0;//為了能通過編譯
14     }
15 };

 

復雜度分析

時間復雜度: O(m),遍歷陣列元素的時間開銷,
空間復雜度: O(m),哈希表的空間消耗,

解法三 隨機演算法

解題思路

這時候面試官又說了,你這解法二空間復雜度連解法一都不如,再想想有沒有更好的解法,
手扶下巴,眉頭一皺,我們又想到,由于多數元素是指在陣列中出現次數大于?n/2? 的元素,因此如果我們隨機選取陣列中的一個元素,那么將有超過1/2的概率選到該多數元素,于是可以使用這種演算法:

演算法

1.在陣列中隨機挑選一個元素;
2.遍歷陣列統計該元素出現次數,若超過陣列元素數的一半,回傳該元素,否則重新隨機挑選一個元素,

代碼

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         int m = nums.size();//計算陣列元素數
 5         srand(time(NULL));//設定亂數種子
 6         int n;//存盤亂數
 7         int count = 0;//初始化以亂數為下標的元素的出現次數為0
 8         while(count<=m/2){//當以亂數為下標的元素出現次數未超過陣列元素數的一般
 9             n = rand()%m;//獲取一個亂數
10             count = 0;//初始化以亂數為下標的元素出現次數為0
11             for(int num : nums) if(num == nums[n]) ++count;//統計以亂數為下標的元素出現次數
12         }
13         return nums[n];//若以該亂數為下標的元素出現次數超過陣列元素數的一半,回傳以該亂數為下標的元素
14     }
15 };

 

復雜度分析

時間復雜度: O(m),理論上最壞情況下復雜度為O(∞),但實際上由于多數元素出現次數超過陣列元素數的一半,平均情況下只需要兩次就能選出多數元素,主要的時間開銷是統計出現次數,其時間復雜度為O(m),
空間復雜度: O(1),只需常數個額外空間,

解法四 摩爾投票法

解題思路

面試官覺得你這解法很有意思,然后又問,那要我就是非酋呢,那豈不是無限回圈了,有沒有更好的辦法,
這下可讓人犯了難,有什么更好的辦法既能時間最優又能空間最優呢?
考慮這樣一個場景,一群人打擂臺,人群中分為不同的幫派,挨個上臺比武,留在臺上的幫派為擂主幫派,如果上臺的人不是自己幫派的人,則將其干掉,代價是損失一個幫派成員;如果上臺的人是自己幫派的人,則將其留下,則當所有人都參與完比武后,留在臺上的必然可以是人數超過比武人數一半的幫派,而在本題中,多數元素出現次數超過陣列元素數的一半,也即,其他所有元素加起來都沒多數元素多,如果我們記多數元素的值為1,其他元素的值為0,將陣列中所有元素值相加,結果必然大于0,于是我們可以設計這樣一種演算法:

演算法

1.初始化候選答案ans為nums[0],初始化數值計算結果count為0;
2.遍歷陣列若該元素與備選答案相等,count加一,否則減一;
3.若count減為零,更換備選答案ans為當前元素,重置count為1,繼續遍歷后續元素,
遍歷完成后回傳最終的ans即為多數元素,

代碼

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         int ans = nums[0];//初始化候選答案為nums[0]
 5         int count = 0;//初始化數值計算結果為0
 6         for(auto num : nums){//遍歷陣列
 7             if(num==ans) ++count;//若該元素與備選答案相同,則count加一
 8             else{//否則減一
 9                 --count;
10                 if(count==0){//若count減為0
11                     ans = num;//更換備選答案為當前元素
12                     ++count;//重置count為1
13                 }
14             }
15         }
16         return ans;//回傳答案
17     }
18 };

 

復雜度分析

時間復雜度: O(m),只需要對陣列進行一次遍歷即可
空間復雜度: O(1),只需常數個額外空間,

Tips:

由于題目明確說明給定的陣列中總是存在多數元素,因此本題不用考慮陣列不存在多數元素的情況,若未做說明,需要像解法三那樣,在選出ans以后再進行一次統計,驗證該元素是否是多數元素,若果是,回傳之;如果不是,回傳不存在多數元素,時間復雜度和空間空間復雜度不變,

更多知識內容分享:

力扣個人主頁https://leetcode-cn.com/profile/articles/
CSDN個人主頁https://blog.csdn.net/qq_39255924
牛客個人主頁https://blog.nowcoder.net/newcoderthewarrior

可可愛愛的蕾姆鎮
image

轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/404041.html

標籤:C++

上一篇:Python基礎(二十):pip命令大全

下一篇:返回列表

標籤雲
其他(134788) Python(24123) JavaScript(15056) Java(14610) C(11097) 區塊鏈(8165) AI(6813) 基礎類(6313) MySQL(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4188) Linux(4089) PHP(3814) C#(3716) 爪哇(3561) html(3374) C語言(3288) C++語言(3117) sql(3024) R(2776) 熊猫(2774) Java相關(2746) 数组(2739) 疑難問題(2699) 反应(2482) 單片機工控(2479) css(2105) 数据框(1968) Web開發(1951) 节点.js(1938) VBA(1919) 網絡通信(1793) 蟒蛇-3.x(1774) 數據庫相關(1767) VB基礎類(1755) .NETCore(1649) ASP.NET(1648) 開發(1646) 系統維護與使用區(1617) 列表(1581) 基礎和管理(1579) json(1568) C++(1567) JavaEE(1566) 安卓(1523) 專題技術討論區(1515) HtmlCss(1500) Windows客戶端使用(1484) 扑(1469) iOS(1430) 查询(1408) 打字稿(1376) Unity3D(1366) VCL組件開發及應用(1353) .NET技术(1340) sql-server(1287) Qt(1283) 细绳(1226) HTML(CSS)(1220)

熱門瀏覽
  • 【C++】Microsoft C++、C 和匯編程式檔案

    ......

    uj5u.com 2020-09-10 00:57:23 more
  • 例外宣告

    相比于斷言適用于排除邏輯上不可能存在的狀態,例外通常是用于邏輯上可能發生的錯誤。 例外宣告 Item 1:當函式不可能拋出例外或不能接受拋出例外時,使用noexcept 理由 如果不打算拋出例外的話,程式就會認為無法處理這種錯誤,并且應當盡早終止,如此可以有效地阻止例外的傳播與擴散。 示例 //不可 ......

    uj5u.com 2020-09-10 00:57:27 more
  • Codeforces 1400E Clear the Multiset(貪心 + 分治)

    鏈接:https://codeforces.com/problemset/problem/1400/E 來源:Codeforces 思路:給你一個陣列,現在你可以進行兩種操作,操作1:將一段沒有 0 的區間進行減一的操作,操作2:將 i 位置上的元素歸零。最終問:將這個陣列的全部元素歸零后操作的最少 ......

    uj5u.com 2020-09-10 00:57:30 more
  • UVA11610 【Reverse Prime】

    本人看到此題沒有翻譯,就附帶了一個自己的翻譯版本 思考 這一題,它的第一個要求是找出所有 $7$ 位反向質數及其質因數的個數。 我們應該需要質數篩篩選1~$10^{7}$的所有數,這里就不慢慢介紹了。但是,重讀題,我們突然發現反向質數都是 $7$ 位,而將它反過來后的數字卻是 $6$ 位數,這就說明 ......

    uj5u.com 2020-09-10 00:57:36 more
  • 統計區間素數數量

    1 #pragma GCC optimize(2) 2 #include <bits/stdc++.h> 3 using namespace std; 4 bool isprime[1000000010]; 5 vector<int> prime; 6 inline int getlist(int ......

    uj5u.com 2020-09-10 00:57:47 more
  • C/C++編程筆記:C++中的 const 變數詳解,教你正確認識const用法

    1、C中的const 1、區域const變數存放在堆疊區中,會分配記憶體(也就是說可以通過地址間接修改變數的值)。測驗代碼如下: 運行結果: 2、全域const變數存放在只讀資料段(不能通過地址修改,會發生寫入錯誤), 默認為外部聯編,可以給其他源檔案使用(需要用extern關鍵字修飾) 運行結果: ......

    uj5u.com 2020-09-10 00:58:04 more
  • 【C++犯錯記錄】VS2019 MFC添加資源不懂如何修改資源宏ID

    1. 首先在資源視圖中,添加資源 2. 點擊新添加的資源,復制自動生成的ID 3. 在解決方案資源管理器中找到Resource.h檔案,編輯,使用整個專案搜索和替換的方式快速替換 宏宣告 4. Ctrl+Shift+F 全域搜索,點擊查找全部,然后逐個替換 5. 為什么使用搜索替換而不使用屬性視窗直 ......

    uj5u.com 2020-09-10 00:59:11 more
  • 【C++犯錯記錄】VS2019 MFC不懂的批量添加資源

    1. 打開資源頭檔案Resource.h,在其中預先定義好宏 ID(不清楚其實ID值應該設定多少,可以先新建一個相同的資源項,再在這個資源的ID值的基礎上遞增即可) 2. 在資源視圖中選中專案資源,按F7編輯資源檔案,按 ID 型別 相對路徑的形式添加 資源。(別忘了先把檔案拷貝到專案中的res檔案 ......

    uj5u.com 2020-09-10 01:00:19 more
  • C/C++編程筆記:關于C++的參考型別,專供新手入門使用

    今天要講的是C++中我最喜歡的一個用法——參考,也叫別名。 參考就是給一個變數名取一個變數名,方便我們間接地使用這個變數。我們可以給一個變數創建N個參考,這N + 1個變數共享了同一塊記憶體區域。(參考型別的變數會占用記憶體空間,占用的記憶體空間的大小和指標型別的大小是相同的。雖然參考是一個物件的別名,但 ......

    uj5u.com 2020-09-10 01:00:22 more
  • 【C/C++編程筆記】從頭開始學習C ++:初學者完整指南

    眾所周知,C ++的學習曲線陡峭,但是花時間學習這種語言將為您的職業帶來奇跡,并使您與其他開發人員區分開。您會更輕松地學習新語言,形成真正的解決問題的技能,并在編程的基礎上打下堅實的基礎。 C ++將幫助您養成良好的編程習慣(即清晰一致的編碼風格,在撰寫代碼時注釋代碼,并限制類內部的可見性),并且由 ......

    uj5u.com 2020-09-10 01:00:41 more
最新发布
  • 【Warrior刷題筆記】力扣169. 多數元素 【排序 || 哈希 || 隨機

    題目 來源:力扣(LeetCode) 鏈接:https://leetcode-cn.com/problems/majority-element/ 注意,該題在LC中被標注為easy,所以我們更多應該關注的是文章中不斷優化的思路和方法。很多時候面試考察的,就是與面試官一起做題并把時間復雜度和空間復雜度 ......

    uj5u.com 2022-01-06 06:29:25 more
  • Python基礎(二十):pip命令大全

    pip升級命令:python -m pip install --upgrade pippip install name //這里的name是要安裝的第三方庫名pip install name -i http://mirrors.aliyun.com/pypi/simple/ 國內鏡像源阿里云:http://mirrors.aliyun.com/pypi/simple/ (推薦使用)清華大學:https://pypi.tuna.tsinghua.edu.cn/simple豆瓣:http:/...

    uj5u.com 2022-01-05 21:38:38 more
  • 自學python兩年,漲薪20K,分享學習心得及學習方法

    前言自我介紹一下吧,我是普通專科畢業的學生,學的建筑系。畢業后找了一個公司上班,開始了打工人的生活。勤勤懇懇的作業了兩年后,存款幾萬塊。感覺這樣下去不是辦法,生活無望啊,思考一番后決定轉行。轉行嘛,就是奔著掙錢去的。聽說IT行業工資高,就決定去當程式員。然后我就開始自學python。學習python兩年后,我現在的薪資已經漲了20K。編程入門我剛開始學習編程,主要是因為自己想動手做個網站,但是由于技術原因,再加上朋友都比較忙,最后抱著“求人不如求己”的想法,干脆自學。編程難不難?這個問題我覺得所有...

    uj5u.com 2022-01-05 21:38:18 more
  • selenium--&ldquo;PO+關鍵字&ldquo;教你速成簡單的自動化測驗框

    簡單的實戰代碼教程,一看就會...

    uj5u.com 2022-01-05 21:38:02 more
  • 決議C++ STL容器list區別于Python的list

    C++ STL list是序列容器,允許在序列內的任何地方進行恒定時間插入和擦除操作,以及雙向迭代。串列容器被實作為雙向鏈表;雙向鏈表可以將它們包含的每個元素存盤在不同且不相關的存盤位置。排序是通過與指向它前面元素的鏈接和指向它后面元素的鏈接的每個元素的關聯在內部保持的。...

    uj5u.com 2022-01-05 21:37:48 more
  • 如果一名程式員一個月拿兩萬,得知一對夫婦賣豬肉可以賺五萬一個月

    在知乎上看到這么個帖子,覺得挺有意思,大家一起瞧瞧?對此,我也看到了許多犀利的回答哈**A:**我反過來問你,如果一對夫婦賣豬肉一個月只能掙一萬,聽說一名程式員一個月拿五萬,他們能選擇去當程式員拿五萬嗎?這時候你知道不是誰都能當程式員,不是哪個程式員都能拿五萬了,那你怎么就覺得誰都能賣豬肉、誰賣豬肉都能賺五萬一個月了?你拿得動刀嗎?你有超過常人的進貨和銷售渠道嗎?你有人家的口碑嗎?**B:**有時候可能會有一些莫名的優越感,將這個世界按照一條線性的賽道來理解,就像從小到大好好學習,一路考大學,唯一的...

    uj5u.com 2022-01-05 21:36:52 more
  • 阿里云大學>【Python學習路線】Python語言基礎自測考試 - 初級難

    來一起驗證開發者身份吧!~...

    uj5u.com 2022-01-05 21:36:32 more
  • python爬蟲詳解(三)&mdash;&mdash;爬取世界常用密碼并保存到字典內

    今天的爬蟲有點特別,先爬取文本,然后base64解碼,然后再存盤至文本字典內點個贊留個關注吧!!首先我們需要爬取網站鏈接代碼如下:爬取后我們只要password=內容,只要內容,不需要鏈接,所以我們這里使用了res_6 = re.findall('password=(.*)', e) #爬取密碼鏈接password=?# -*- coding: utf-8 -*-from bs4 import BeautifulSoupimport reimport reques....

    uj5u.com 2022-01-05 21:36:10 more
  • 90后,要有多少存款才正常?答案太扎心了

    昨天晚上,群里一個小伙伴分享了一個話題,標題就很扎心:90后,要有多少存款才正常?話題底下,網友們貢獻了近3000條“成績單”。@鳴子:95后,作業3年,存款20萬,攢錢還在進行中。@西瓜氣泡水:92年,存款27萬,同齡人中不算多,目前壓力也不算大。@曉然:我是90年的,未婚,目前存款53萬,作為獨立女性,我覺得結不結婚不重要,有錢才重要。…看到這里我心里一萬個崩潰。好在也不止我一個,評論底下還有一群倔強青銅。沒有對比就沒有傷害。一路同行的90后,不知不覺間已經隔了好幾道分水嶺。...

    uj5u.com 2022-01-05 21:34:39 more
  • 非科班,低學歷的我如何自學 Python ,找到一份月薪15K的作業?

    背景本人專科畢業(報了自考本科),會計專業,經朋友介紹一次很偶然的機會,接觸到了這個行業,今天是我Kotlin入門后,入行Python后,第一次總結下自己的經驗!17年從野雞大學畢業后,剛開始接觸的Java,后來入門了Kotlin,后來我自學Python,成功入行,現在已經在新的公司干了大半年了!昨天我分享了別人為什么學習 Python ?的文章,只是以Python 語言本身的特性來描述了這個理由,今天就來說說我自己。1.為什么學Python?相信能進來看這篇體會小文的人,都是因為作業或者興趣要學習...

    uj5u.com 2022-01-05 21:34:06 more