Majority Element

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，意味著它一定會出現在排序後數組的中間位置

排序後取中位數

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

利用數學證明

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

解決方案

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];
}

import { describe, expect, it } from 'vitest';
import { majorityElement } from './solution';

describe('169. Majority Element', () => {
  const testCases = [
    {
      nums: [3, 2, 3],
      expected: 3,
      description: 'Basic case: 3 appears 2 times, more than half',
    },
    {
      nums: [2, 2, 1, 1, 1, 2, 2],
      expected: 2,
      description: 'Longer array: 2 appears 4 times, more than half',
    },
    {
      nums: [1],
      expected: 1,
      description: 'Edge case: only one element',
    },
    {
      nums: [1, 1, 1, 1, 1, 2, 2],
      expected: 1,
      description: 'Majority element in first half',
    },
  ];

  testCases.forEach(({ nums, expected, description }) => {
    it(description, () => {
      expect(majorityElement(nums)).toBe(expected);
    });
  });
});

排序法解析

這個解法基於一個重要的數學觀察：如果一個元素出現次數大於 n/2，那麼在排序後的數組中，它一定會佔據中間位置。

數學證明

引理: 如果元素 x 出現次數 > n/2，那麼 sortedArray[⌊n/2⌋] = x

證明:

設元素 x 出現 k 次，其中 k > n/2
在排序後的數組中，x 的所有出現都會聚集在一起
由於 k > n/2，x 至少會佔據從某個位置開始的連續 k 個位置
無論 x 從哪個位置開始出現，都會跨越中間位置 ⌊n/2⌋

複雜度分析

時間複雜度: O(n log n) - 主要來自排序操作
空間複雜度: O(1) - 使用 toSorted() 不修改原數組，但會創建新數組

使用 toSorted() 而不是 sort() 是為了避免修改原數組，這是函數式編程的良好實踐

其他解法比較

方法	時間複雜度	空間複雜度	優缺點
排序法	O(n log n)	O(1)	簡單易懂，但不是最優
Hash Map	O(n)	O(n)	直觀，但需要額外空間
Boyer-Moore	O(n)	O(1)	最優解，但較難理解

Boyer-Moore 投票算法 (進階)

function majorityElementOptimal(nums: number[]): number {
  let candidate = nums[0];
  let count = 1;
  
  for (let i = 1; i < nums.length; i++) {
    if (count === 0) {
      candidate = nums[i];
      count = 1;
    } else if (nums[i] === candidate) {
      count++;
    } else {
      count--;
    }
  }
  
  return candidate;
}

這個算法的思想是：多數元素的出現次數比其他所有元素的總和還多，因此在"對消"過程中，多數元素最終會勝出。

實際應用

選舉系統中的多數票統計
數據流中的頻繁項目檢測
分散式系統中的一致性投票
錯誤檢測和糾正系統