[LeetCode] 169. Majority Element 解題思路 (Easy)

這題要算出重複最多的數字。

LeetCode 題目連結

 

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

 

題目

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.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

Accept 作法

我弄得 flag 很多，可能有更好的做法，目前尚未去看別人的作法。


Runtime: 1225 ms
Memory: 42.2 MB

Java 程式碼

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        
        int currentNum = nums[0];
        int currentCount = 0;
        int lastCount = 0;
        int lastNum = nums[0];
        boolean isFirst = true;
        for(int num:nums){
            if(currentNum == num && !isFirst){
               currentCount++; 
            }else{
                currentCount=0;
            }
          
            
            if(currentCount > lastCount){
                
                lastCount = currentCount;
                lastNum = num;
                
            }
            
            if(isFirst){
                isFirst = false;
            }
            currentNum = num;
        }
        return lastNum;
    }
}

 

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題