亚洲黄色视频在线观看网站,婷婷无码片,一级黄色毛片,日日摸日日碰夜夜爽2015电影,无遮挡黄视频,熟女网址,gb主奴抽打鞭菊惩罚调教,一级黄色录像播放

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問(wèn)題叫做?多數(shù)元素??，我們先來(lái)看題面：

https://leetcode-cn.com/problems/majority-element/

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ?n / 2? times. You may assume that the majority element always exists in the array.

題意

給定一個(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

解題

https://benym.cn/2020/07/15/LeetCode-169-%E5%A4%9A%E6%95%B0%E5%85%83%E7%B4%A0/

方法1、哈希表：

利用一個(gè)哈希表計(jì)算頻率，當(dāng)元素的頻率大于nums.length/2的時(shí)候就是要找的元素

class?Solution?{
????public?int?majorityElement(int[] nums)?{
????????int?len = nums.length;
????????int?res = Integer.MIN_VALUE;
????????Map map?= new?HashMap<>();
????????for(int?num:nums){
????????????map.put(num,map.getOrDefault(num,0)+1);
????????}
????????for(Map.Entry entry: map.entrySet()){
????????????if(entry.getValue()>len/2){
????????????????res = entry.getKey();
????????????}
????????}
????????return?res;
????}
}

方法2、排序：

由于多數(shù)元素在數(shù)組中出現(xiàn)的次數(shù)大于n/2，于是可以將數(shù)組排序，對(duì)應(yīng)nums.length/2的位置就是這個(gè)多數(shù)元素

class?Solution?{
????public?int?majorityElement(int[] nums)?{
????????Arrays.sort(nums);
????????return?nums[nums.length/2];
????}
}

方法3、摩爾計(jì)數(shù)法：

候選人(cand_num)初始化為nums[0]，票數(shù)count初始化為1。
當(dāng)遇到與cand_num相同的數(shù)，則票數(shù)count = count + 1，否則票數(shù)count = count - 1。
當(dāng)票數(shù)count為0時(shí)，更換候選人，并將票數(shù)count重置為1。
遍歷完數(shù)組后，cand_num即為最終答案。

為何這行得通呢？
投票法是遇到相同的則票數(shù) + 1，遇到不同的則票數(shù) - 1。
且“多數(shù)元素”的個(gè)數(shù)> ? n/2 ?，其余元素的個(gè)數(shù)總和<= ? n/2 ?。
因此“多數(shù)元素”的個(gè)數(shù) - 其余元素的個(gè)數(shù)總和的結(jié)果肯定 >= 1。
這就相當(dāng)于每個(gè)“多數(shù)元素”和其他元素兩兩相互抵消，抵消到最后肯定還剩余至少1個(gè)“多數(shù)元素”。

無(wú)論數(shù)組是1 2 1 2 1，亦或是1 2 2 1 1，總能得到正確的候選人。

class?Solution?{
????public?int?majorityElement(int[] nums)?{
????????int?cand_num = nums[0], count = 1;
????????for?(int?i = 1; i < nums.length; ++i) {
????????????if?(cand_num == nums[i])
????????????????++count;
????????????else?if?(--count == 0) {
????????????????cand_num = nums[i];
????????????????count = 1;
????????????}
????????}
????????return?cand_num;
????}
}

好了，今天的文章就到這里，如果覺(jué)得有所收獲，請(qǐng)順手點(diǎn)個(gè)在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動(dòng)力。

上期推文：

LeetCode1-160題匯總，希望對(duì)你有點(diǎn)幫助！

LeetCode刷題實(shí)戰(zhàn)161：相隔為1的編輯距離

LeetCode刷題實(shí)戰(zhàn)162：尋找峰值

LeetCode刷題實(shí)戰(zhàn)163：缺失的區(qū)間

LeetCode刷題實(shí)戰(zhàn)164：最大間距

LeetCode刷題實(shí)戰(zhàn)165：比較版本號(hào)

LeetCode刷題實(shí)戰(zhàn)166：分?jǐn)?shù)到小數(shù)

LeetCode刷題實(shí)戰(zhàn)167：兩數(shù)之和 II - 輸入有序數(shù)組

LeetCode刷題實(shí)戰(zhàn)168：Excel表列名稱

?LeetCode刷題實(shí)戰(zhàn)169：多數(shù)元素

題意

解題