169. 多數(shù)元素
難度：簡(jiǎn)單
給定一個(gè)大小為 *n *的數(shù)組肿仑，找到其中的多數(shù)元素赞辩。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ? n/2 ? 的元素。
你可以假設(shè)數(shù)組是非空的虎忌，并且給定的數(shù)組總是存在多數(shù)元素。
示例 1：
輸入：[3,2,3]
輸出：3
示例 2：
輸入：[2,2,1,1,1,2,2]
輸出：2
進(jìn)階：
- 嘗試設(shè)計(jì)時(shí)間復(fù)雜度為 O(n)憋飞、空間復(fù)雜度為 O(1) 的算法解決此問題同规。
通過次數(shù)：284,001
提交次數(shù)：431,167
這是我第一次寫解題博客，之所以有感而發(fā)咧擂，也許是因?yàn)檫@道題算法的奇妙之處逞盆。先上代碼~~~
class Solution {
public:
int majorityElement(vector<int>& nums)
{
if (nums.empty())
return 0;
if (nums.size()==1)
return nums[0];
int count = 1;
sort(nums.begin(), nums.end());//進(jìn)行排序，以便之后進(jìn)行計(jì)數(shù)疊加
int std = nums[0];//起初以第一個(gè)數(shù)為基準(zhǔn)
for (int i = 1; i < nums.size(); i++)
{
if (nums[i] == std)
{
count++;
if (count > nums.size() / 2)
return nums[i];
}
else
{
std = nums[i];//需更換基準(zhǔn)數(shù)
count = 1;
}
}
return 0;
}
};
image.png
效率還是太低松申，于是我開始想了解大佬們的思路云芦，在此做了一下簡(jiǎn)單的總結(jié)~~~
一、排序
這是我最佩服的了贸桶，沒有之一
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
};
“題中說了給定的數(shù)組總是存在多數(shù)元素舅逸。，也就是說肯定有一個(gè)元素的個(gè)數(shù)大于數(shù)組長(zhǎng)度的一半皇筛。我們只需要把這個(gè)數(shù)組排序琉历，那么數(shù)組中間的值肯定是存在最多的元素。”
看看人家水醋，再看看我旗笔，嘖嘖嘖，日后還需努力練習(xí)拄踪，天道酬勤
二蝇恶、摩爾投票法
public:
int moreThanHalfNum_Solution(vector<int>& nums) {
int val, cnt = 0;
for (auto x : nums)
{
if (!cnt) val = x, cnt ++ ; //目標(biāo)值與其他值剛好配對(duì)抵消時(shí)，重置計(jì)數(shù)
else
{
if (x == val) cnt ++ ;
else cnt -- ;
}
}
return val; //最后剩下的一定是多于半數(shù)的目標(biāo)值
}
};
“不同的兩數(shù)相互抵消惶桐，最后剩下的肯定是多于一半的那個(gè)數(shù)艘包。”
三、哈希數(shù)組
class Solution {
public:
int majorityElement(vector<int>& nums) {
//建立哈希數(shù)組找其中出現(xiàn)次數(shù)大于n/2的數(shù)
unordered_map<int,int> hash;
int res=0;
int len=nums.size();
for(int i=0;i<len;i++){
hash[nums[i]]++;
if(hash[nums[i]]>len/2){
res=nums[i];
break;//優(yōu)化一下
}
}
return res;
}
};
