Majority Element
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.length1 <= n <= 5 * 10⁴-10⁹ <= nums[i] <= 10⁹
解題思路
理解多數元素性質 多數元素出現次數 > n/2，意味著它一定會出現在排序後數組的中間位置
排序後取中位數 排序後，位於中間位置的元素必然是多數元素
解決方案
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];
}