婷婷久久免费视频,99在线观看免费视频,黄色国产精品,日韩另类大片,青青草视频在线网站,国产日韩在线电影,久久露脸国语精品国产91,一区二区三区免费播放

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

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

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.

題意

給定一個大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ? n/2 ? 的元素。

你可以假設數(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、哈希表：

利用一個哈希表計算頻率，當元素的頻率大于nums.length/2的時候就是要找的元素

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ù)組排序，對應nums.length/2的位置就是這個多數(shù)元素

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

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

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

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

無論數(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;
????}
}

好了，今天的文章就到這里，如果覺得有所收獲，請順手點個在看或者轉發(fā)吧，你們的支持是我最大的動力。

上期推文：

LeetCode1-160題匯總，希望對你有點幫助！

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

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

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

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

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

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

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

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

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

題意

解題