Majority Element

February 11, 2025•--

Find the element that appears more than n/2 times using sorting approach

Find the element that appears more than half the time in an array

問題描述

給定一個大小為 n 的數組 nums，返回其中的多數元素。多數元素是指在數組中出現次數大於 ⌊n/2⌋ 的元素。

你可以假設數組是非空的，並且給定的數組總是存在多數元素。

範例

輸入：nums = [3,2,3]
輸出：3

輸入：nums = [2,2,1,1,1,2,2]
輸出：2

限制條件

n == nums.length
1 <= n <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹

解題思路

理解多數元素性質多數元素出現次數 >

n/2，意味著它一定會出現在排序後數組的中間位置

### 排序後取中位數排序後，位於中間位置的元素必然是多數元素

利用數學證明由於多數元素佔據超過一半的位置，中間位置必然被多數元素佔據

解決方案

typescript

export function majorityElement(nums: number[]): number {
  // Sort and take the middle value as the majority element
  // Since majority element appears > n/2 times, the middle value after sorting is guaranteed to be it
  const midIndex = Math.floor(nums.length / 2);
  const sortedNums = nums.toSorted((a, b) => a - b);
 
return sortedNums[midIndex];
}