成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Majority Element 眾數(shù)

sihai / 1844人閱讀

摘要：排序法復(fù)雜度時(shí)間空間思路將數(shù)組排序，這時(shí)候數(shù)組最中間的數(shù)肯定是眾數(shù)。投票法復(fù)雜度時(shí)間空間思路記錄一個(gè)變量，還有一個(gè)變量，開始遍歷數(shù)組。代碼投票法復(fù)雜度時(shí)間空間思路上一題中，超過一半的數(shù)只可能有一個(gè)，所以我們只要投票出一個(gè)數(shù)就行了。

Majority Element I 
Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.


You may assume that the array is non-empty and the majority element always exist in the array.
哈希表法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

在遍歷數(shù)組的過程中，用一個(gè)哈希表記錄每個(gè)數(shù)出現(xiàn)過的次數(shù)，如果該次數(shù)大于一半，則說明是眾數(shù)。

排序法 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(1)

思路

將數(shù)組排序，這時(shí)候數(shù)組最中間的數(shù)肯定是眾數(shù)。

代碼 
public class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}
位操作法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

假設(shè)一個(gè)數(shù)是最多只有32位的二進(jìn)制數(shù)，那么我們從第一位到第32位，對(duì)每一位都計(jì)算所有數(shù)字在這一位上1的個(gè)數(shù)，如果這一位1的個(gè)數(shù)大于一半，說明眾數(shù)的這一位是1，如果小于一半，說明大多數(shù)的這一位是0。

投票法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

記錄一個(gè)candidate變量，還有一個(gè)counter變量，開始遍歷數(shù)組。如果新數(shù)和candidate一樣，那么counter加上1，否則的話，如果counter不是0，則counter減去1，如果counter已經(jīng)是0，則將candidate更新為這個(gè)新的數(shù)。因?yàn)槊恳粚?duì)不一樣的數(shù)都會(huì)互相消去，最后留下來的candidate就是眾數(shù)。

代碼 
public class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0], cnt = 0;
        for(int i = 1; i < nums.length; i++){
            if(candidate == nums[i]){
                cnt++;
            } else if(cnt==0){
                candidate = nums[i];
            } else {
                cnt--;
            }
        }
        return candidate;
    }
}
Majority Element II 
Given an integer array of size n, find all elements that appear more than ? n/3 ? times. The algorithm should run in linear time and in O(1) space.
投票法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

上一題中，超過一半的數(shù)只可能有一個(gè)，所以我們只要投票出一個(gè)數(shù)就行了。而這題中，超過n/3的數(shù)最多可能有兩個(gè)，所以我們要記錄出現(xiàn)最多的兩個(gè)數(shù)。同樣的兩個(gè)candidate和對(duì)應(yīng)的兩個(gè)counter，如果遍歷時(shí)，某個(gè)候選數(shù)和到當(dāng)前數(shù)相等，則給相應(yīng)計(jì)數(shù)器加1。如果兩個(gè)計(jì)數(shù)器都不為0，則兩個(gè)計(jì)數(shù)器都被抵消掉1。如果某個(gè)計(jì)數(shù)器為0了，則將當(dāng)前數(shù)替換相應(yīng)的候選數(shù)，并將計(jì)數(shù)器初始化為1。最后我們還要遍歷一遍數(shù)組，確定這兩個(gè)出現(xiàn)最多的數(shù)，是否都是眾數(shù)。

代碼 
public class Solution {
    public List majorityElement(int[] nums) {
        List res = new ArrayList();
        if(nums.length == 0) return res;
        int c1 = 1, c2 = 0, n1 = nums[0], n2 = 0;
        for(int i = 1; i < nums.length; i++){
            // 如果和某個(gè)候選數(shù)相等，將其計(jì)數(shù)器加1
            if(nums[i] == n1){
                c1++;
            } else if(nums[i] == n2){
                c2++;
            // 如果都不相等，而且計(jì)數(shù)器都不為0，則計(jì)數(shù)器都減1
            } else if(c1 != 0 && c2 != 0){
                c1--;
                c2--;
            // 如果某個(gè)計(jì)數(shù)器為0，則更新相應(yīng)的候選數(shù)
            } else {
                if(c1 == 0){
                    n1 = nums[i];
                    c1 = 1;
                } else {
                    n2 = nums[i];
                    c2 = 1;
                }
            }
        }
        c1 = 0;
        c2 = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == n1) c1++;
            else if(nums[i] == n2) c2++;
        }
        if(c1 > nums.length / 3) res.add(n1);
        if(c2 > nums.length / 3) res.add(n2);
        return res;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64506.html

相關(guān)文章

  • LeetCode 之 JavaScript 解答第169題 —— 求眾數(shù) I（Majority El

    摘要：小鹿題目算法思路摩爾投票算法題目的要求是讓我們求數(shù)組中超過一半數(shù)據(jù)以上相同的元素且總是存在的。 Time：2019/4/4Title: Majority Element 1Difficulty: easyAuthor: 小鹿 題目：Majority Element 1 Given an array of size n, find the majority element. The ...

    hightopo 評(píng)論0 收藏0

  • leetcode 169 Majority Element

    摘要：因?yàn)楸姅?shù)出現(xiàn)的次數(shù)必定大于，所以我們只要取第個(gè)位置上的元素，這個(gè)元素一定為我們要找的眾數(shù)。 題目詳情 Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.You may assume th...

    tangr206 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第229題 —— 求眾數(shù) II（Majority E

    摘要：繼續(xù)使用摩投票算法，假設(shè)要投票，選取票數(shù)超過以上選為候選人，一個(gè)被分為三等份，也就是說最多有兩位當(dāng)選人。排序解決先進(jìn)行一次排序快排，然后遍歷數(shù)據(jù)，找出滿足條件的數(shù)據(jù)。 Time：2019/4/5Title: Majority Element 2Difficulty: mediumAuthor: 小鹿 問題：Majority Element 2 Given an integer ar...

    BearyChat 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • leetcode講解--169. Majority Element

    摘要：當(dāng)時(shí)題目改成了小明收紅包，找出現(xiàn)次數(shù)超過一般的那個(gè)紅包，要求線性時(shí)間復(fù)雜度，也就是說不能用排序排序算法最優(yōu)情況是。另外這個(gè)題在上的難度是哦，好傷心啊，當(dāng)初的我連這題都沒想出解法，真是夠年輕啊。 169. Majority Element Given an array of size n, find the majority element. The majority element i...

    LiuRhoRamen 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<