多数元素（LeetCode169）

题目描述

在这道题中，我们需要找到一个数组中的多数元素。多数元素指的是在数组中出现次数大于 ⌊ n/2 ⌋ 的元素，其中 n 是数组的长度。你可以假设数组是非空的，并且总是存在多数元素。

例如：

• 示例 1：
  • 输入：nums = [3,2,3]
  • 输出：3
• 示例 2：
  • 输入：nums = [2,2,1,1,1,2,2]
  • 输出：2

解决思路

方法一：排序法

通过对数组进行排序，数组中间的元素必定是多数元素，因为多数元素出现的次数超过数组长度的一半。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  nums.sort((a, b) => a - b);
  return nums[Math.floor(nums.length / 2)];
};

// 测试用例
console.log(majorityElement([3, 2, 3])); // 输出: 3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 输出: 2

方法二：哈希表法

遍历整个数组，每个元素作为键存入哈希表中，值为出现的次数。最后遍历哈希表，找到出现次数最多的元素。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = function(nums) {
  const map = new Map();
  for (let num of nums) {
    map.set(num, (map.get(num) || 0) + 1);
  }

  let result = null;
  let maxCount = 0;
  for (let [num, count] of map.entries()) {
    if (count > maxCount) {
      maxCount = count;
      result = num;
    }
  }

  return result;
};

// 测试用例
console.log(majorityElement([3, 2, 3])); // 输出: 3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 输出: 2

方法三：分治法

通过递归将数组分成两部分，分别找出每部分的多数元素，然后比较这两个多数元素在整个数组中的出现次数。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {
  function majorityElementRec(lo, hi) {
    if (lo === hi) {
      return nums[lo];
    }

    const mid = Math.floor((hi - lo) / 2) + lo;
    const leftMajority = majorityElementRec(lo, mid);
    const rightMajority = majorityElementRec(mid + 1, hi);

    if (leftMajority === rightMajority) {
      return leftMajority;
    }

    const leftCount = countInRange(nums, leftMajority, lo, hi);
    const rightCount = countInRange(nums, rightMajority, lo, hi);

    return leftCount > rightCount ? leftMajority : rightMajority;
  }

  function countInRange(nums, num, lo, hi) {
    let count = 0;
    for (let i = lo; i <= hi; i++) {
      if (nums[i] === num) {
        count++;
      }
    }
    return count;
  }

  return majorityElementRec(0, nums.length - 1);
}

// 测试用例
console.log(majorityElement([3, 2, 3])); // 输出: 3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 输出: 2

方法四：Boyer-Moore 投票算法

Boyer-Moore 投票算法是一种线性时间复杂度 O(n) 且空间复杂度为 O(1) 的算法，专门用于解决多数元素问题。该算法基于以下理念：

• 如果一个元素是多数元素，那么它出现的次数一定比其他所有元素出现次数的总和还多。
• 我们可以通过“投票”的方式来找到这个多数元素。

算法步骤

1. 初始化候选人 candidate 为 null，计票器 count 为 0。
2. 遍历数组：
   • 如果 count 为 0，则将当前元素设置为 candidate，并将 count 设置为 1。
   • 如果当前元素等于 candidate，则 count 增加 1。
   • 如果当前元素不等于 candidate，则 count 减少 1。
3. 遍历结束后，candidate 就是数组中的多数元素。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {
  let candidate = null;
  let count = 0;

  for (let num of nums) {
    if (count === 0) {
      candidate = num;
      count = 1;
    } else if (num === candidate) {
      count++;
    } else {
      count--;
    }
  }

  return candidate;
}

// 测试用例
console.log(majorityElement([3, 2, 3])); // 输出: 3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 输出: 2
console.log(majorityElement([12, 2, 3, 1, 1, 1, 1])); // 输出: 1

代码解释

1. 排序法：通过排序将数组中所有元素按顺序排列，中间位置的元素必定是多数元素。
2. 哈希表法：使用哈希表记录每个元素的出现次数，最终返回出现次数最多的元素。
3. 分治法：递归地将数组分成两部分，分别找出每部分的多数元素，最后比较这两个多数元素在整个数组中的出现次数。
4. Boyer-Moore 投票算法：通过投票机制找出多数元素。如果一个元素是多数元素，那么它的出现次数一定比其他所有元素的出现次数总和还多。

总结

本文介绍了四种解决多数元素问题的方法：排序法、哈希表法、分治法和 Boyer-Moore 投票算法。每种方法都有其独特的优势和适用场景。尤其是 Boyer-Moore 投票算法，其线性时间复杂度和常数空间复杂度使其在处理大规模数据时具有显著的优势。