169. Majority Element

📘 題目敘述

給定一個大小為 n 的整數陣列 nums，請回傳其中的 majority element。

majority element 指的是在陣列中出現次數 嚴格大於 ⌊n/2⌋ 的元素。

你可以假設 majority element 一定存在於陣列中。

條件限制

• n == nums.length
• 1 ≤ n ≤ 5 * 10^4
• -10^9 ≤ nums[i] ≤ 10^9

🧠 解題思路

我的想法是利用題目給的關鍵條件：

有一個數字出現次數 超過一半

所以如果我把陣列排序之後：

• 那個出現超過一半的數字，會在排序後的陣列中形成一段很長的連續區間
• 因為它的數量 > n/2，所以這段區間一定會覆蓋到中間位置 n/2
• 因此排序後，直接回傳 nums[n/2] 就一定是答案

所有變數

• nums：輸入陣列（我會先把它排序）
• nums.size()：陣列長度 n
• nums[nums.size() / 2]：排序後的中間位置元素（必定是 majority element）

🪜 主要流程步驟

第一步：排序陣列

• 我先對 nums 進行排序
• 讓相同的數字會集中在一起，形成連續段

第二步：取排序後中間值

• 回傳 nums[n/2]
• 因為 majority element 的數量超過一半，所以它一定佔到中間這格

💡 為什麼這樣一定正確？

• 排序後相同元素一定連續排列
• majority element 的數量 > n/2，因此它佔據的區間必定包含中位數位置
• 所以取排序後的 nums[n/2] 一定是 majority element

時間複雜度為 O(n log n)，空間複雜度為 O(1)（忽略排序所需額外空間）。

💻 程式碼實作

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

🔗 題目連結

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