LeetCode #169 Majority Element 解題思路及翻譯

LeetCode題目翻譯

英文原文如下

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 的陣列 nums，回傳最常出現的元素(值)

最常出現的元素是一個出現超過 [n/2] 次的元素，你可以認定每個陣列中一定會存在這個元素

來看下範例

這題的意思與範例都蠻容易理解的

範例1中， 2出現了一次，3則出現了兩次， nums.Length則為3，故答案為3 ( 2次 >3÷2 )

範例2中， 2出現了四次，1則出現了三次， nums.Length則為7，故答案為2 ( 4次 >7÷2)

解題思路

第一個方法也比較直覺，迴圈遞迴進去數每個元素各自出現幾次，出現超過 [n/2] 次就回傳

那用C#來實作看看

C# 解決方案

方案1 – 簡單遞迴 + Dictionary

public class Solution {
    public int MajorityElement(int[] nums) {
        
        if(nums.Length == 1)        //陣列只有一個元素就直接回傳
        {
            return nums[0];
        }
        
        //用來存放每個元素出現幾次的紀錄，Key為元素(數字)、Value為出現次數
        Dictionary<int, int> dict = new Dictionary<int, int>();     
        
        int tmp = 0;
        int check = nums.Length/2;
        
        foreach(int num in nums)
        {
            if(dict.ContainsKey(num))     //如果已存在字典內，則幫現在數字加1
            {
                tmp = dict[num]+1;
                if(tmp>check)           //要是出現的次數超過[n/2]次，則回傳結果
                {
                    return num;
                }
                dict[num] = tmp;
            }
            else
            {
                dict.Add(num,1);          //若不存在字典內，幫字典新增
            }
        }
        return -1;
    }
}

實作上選擇用字典以Key Value的方式來查找跟儲存，應該算是比較容易理解的寫法

⭐方案2 – 很簡短的寫法

結果在寫好的兩個禮拜後，筆者在回顧曾經寫過的程式時，突然靈光一閃

既然說明中已經表示「最常出現的元素是一個出現超過 [n/2] 次的元素」

那是不是只要經過排序，中間的那個值就會是答案呢?

舉例來說 :

1121222 ➔ 排序後為 1112222➔ 共7個元素 ➔取第四個元素(index 3)就是答案 : 2

因為那個元素佔了超過一半的長度，所以正中間的元素一定就會是那個元素

程式碼如下 :

public class Solution {
    public int MajorityElement(int[] nums) {
        Array.Sort(nums);               //1.先對陣列進行排列
        return(nums[nums.Length/2]);    //2.直接取index為[nums.Length/2]的元素回傳
    }
}

沒錯，就是這麼的簡潔!

結論

這題比較沒什麼太高的難度，主要是答案2要換位思考一下才能理解而已

這次分享個馬克·吐溫的名言，剛好也跟多數有關

"Whenever you find yourself on the side of the majority,
                               it is time to pause and reflect."
                                                                                                                                               Mark Twain                               

當你發現自己跟多數人站在同一側時，是時候停下來反思一下了

題目連結 : Majority Element – LeetCode

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡可以的話，幫我的FaceBook 粉絲專頁按個讚，我會很感謝的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

最新文章

• LeetCode #2073 Time Needed to Buy Tickets 買到票所需要的時間
• LeetCode #1700 Number of Students Unable to Eat Lunch 吃不到午餐的學生數量
• LeetCode #1544 Make The String Great 讓字串變好
• LeetCode #977 Squares of a Sorted Array 已排序陣列的平方
• LeetCode #283 Move Zeroes 移動零