前端JavaScript多数元素的算法详解

算法介绍

多数元素在一个数组中出现次数超过一半的元素，因此要找到多数元素，需要考虑其出现次数是否超过了数组长度的一半。本文介绍三种常见的多数元素算法，分别为排序法、哈希表法和摩尔投票法。

排序法

排序法的思路是先对数组进行排序，然后返回数组中间的那个元素即可。由于多数元素出现次数超过了数组长度的一半，因此排序后中间的那个元素就是多数元素。

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

实例：

console.log(majorityElement([1, 2, 3, 2, 2, 2, 5, 4, 2])); // 2

哈希表法

哈希表法的思路是使用一个哈希表存储数组中每个元素出现的次数，然后找到出现次数超过数组长度一半的元素。

function majorityElement(nums) {
  let map = new Map();
  for (let num of nums) {
    map.set(num, (map.get(num) || 0) + 1);
    if (map.get(num) > nums.length / 2) {
      return num;
    }
  }
}

实例：

console.log(majorityElement([1, 2, 3, 2, 2, 2, 5, 4, 2])); // 2

摩尔投票法

摩尔投票法的思路是遍历数组，使用一个变量记录当前的众数，如果下一个元素与当前元素相同，则计数器加1，否则计数器减1。当计数器减为0时，将当前元素设置为新的众数。

function majorityElement(nums) {
  let candidate = null;
  let count = 0;
  for (let num of nums) {
    if (count === 0) {
      candidate = num;
    }
    count += (num === candidate) ? 1 : -1;
  }
  return candidate;
}

实例：

console.log(majorityElement([1, 2, 3, 2, 2, 2, 5, 4, 2])); // 2

总结

以上就是三种常见的多数元素算法。排序法时间复杂度为O(nlogn)，哈希表法和摩尔投票法时间复杂度均为O(n)，因此在实际应用中，摩尔投票法是最为高效的解法。