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

資訊專欄INFORMATION COLUMN

leetcode 169 Majority Element

tangr206 / 2875人閱讀

摘要：因為眾數(shù)出現(xiàn)的次數(shù)必定大于，所以我們只要取第個位置上的元素，這個元素一定為我們要找的眾數(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 that the array is non-empty and the majority element always exist in the array.
輸入一個大小為n的數(shù)組，整個數(shù)組里面將會含有一個眾數(shù)，即這個元素出現(xiàn)的次數(shù)大于n/2，我們需要找到并返回這個眾數(shù)
思路

這道題也是一道關(guān)于數(shù)組的重復(fù)元素的問題

首先我想到的辦法是，使用HashMap實現(xiàn)，key是元素的值，value則是這個元素在當(dāng)前出現(xiàn)的次數(shù)，一旦這個次數(shù)大于n/2，我們就可以停止我們的遍歷

但實際上，還有一種更簡單的方法。因為眾數(shù)出現(xiàn)的次數(shù)必定大于n／2，所以我們只要取第n/2個位置上的元素，這個元素一定為我們要找的眾數(shù)。

感謝@SegmentWarrior提供的解法三，不需要建立hashmap所產(chǎn)生的額外空間，同時時間復(fù)雜度為O(n)

解法一 HashMap 
    //HashMap實現(xiàn) 時間復(fù)雜度O(n)
    public int majorityElement(int[] nums) {
        HashMap count = new HashMap();
        int length = nums.length;
        if(length<=1){
            return nums[0];
        }
        for(int i=0;i length/2){
                    return nums[i];
                }
            }else{
                count.put(nums[i], 1);
            }

        }
        
        return -1;
    }
解法二 直接取n/2位置元素 
    //思想：對于一個排序好的數(shù)組，第n/2的位置的元素一定是存在的這個眾數(shù)
    public int majorityElement(int[] nums) {
        
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
解法三 對出現(xiàn)次數(shù)計數(shù) 
    public int majorityElement(int[] nums) {
        int res = nums[0];
        int count = 1;
        
        for(int i=1;i1) count --;
            else res = nums[i];
        }
        return res;
    }

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

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

相關(guān)文章

  • leetcode講解--169. Majority Element

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

    LiuRhoRamen 評論0 收藏0

  • LeetCode[169] Majority Element

    摘要：投票法復(fù)雜度思路設(shè)定一個和這個對應(yīng)的如果一個數(shù)和這個相等，那么就將增加，否則減少的數(shù)目。 LeetCode[169] Majority Element Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2...

    int64 評論0 收藏0

  • 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 評論0 收藏0

  • Leetcode PHP題解--D83 169. Majority Element

    摘要：題目鏈接題目分析給定一個數(shù)組，返回其中出現(xiàn)次數(shù)超過一半的元素。思路用函數(shù)計算元素出現(xiàn)次數(shù)，用逆序排序結(jié)果，輸出第一個即可。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D83 169. Majority Element 題目鏈接 169. Majority Element 題目分析 給定一個數(shù)組，返回其中出現(xiàn)次數(shù)超過一半的元素。 思路 用array_count_values函數(shù)計算...

    yagami 評論0 收藏0

  • Majority Vote Alogrithm（最大投票算法）及其擴展

    摘要：，這是最基礎(chǔ)的最大投票算法。例如，和這兩個數(shù)組最后得到的分別為和，但是這并不影響答案的正確性。接下來，我們可以對這個算法做一些簡單的擴展，我們當(dāng)前定義的的數(shù)量大于的元素。為當(dāng)前出現(xiàn)的次數(shù)。這意味著當(dāng)前這個數(shù)字就是這兩個等待的第三個數(shù)字。 Boyer-Moore：A Linear Time Majority Vote Alogrithm，這是最基礎(chǔ)的最大投票算法。 原文中提到：decid...

    niceforbear 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<