169. 多数元素

题目

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于  ⌊ n/2 ⌋  的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

例

输入: [2,2,1,1,1,2,2]

输出: 2

题解

哈希表

哈希表记录每个元素出现的次数，同时维护一个最大值

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  if (!nums.length) return 0;
  let m = new Map();
  let l = nums.length;
  let mark = { count: 1, val: nums[0] };
  for (let i = 0; i < l; ++i) {
    const cur = nums[i];
    if (!m.has(cur)) {
      m.set(cur, 1);
    } else {
      const c = m.get(cur) + 1;
      if (c >= l / 2) return cur;
      m.set(cur, c);
      if (c > mark.count) {
        mark.count = c;
        mark.val = cur;
      }
    }
  }
  return mark.val;
};

时间复杂度： O(n)

空间复杂度： O(n)

排序

如果是有序数组，重复的数超过一半，那么数组中间肯定是重复数

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

复杂度依赖排序算法

Boyer-Moore 投票算法

如果我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

• 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
• 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
• 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
• 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
• 在遍历完成后，candidate 即为整个数组的众数。

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  let candidate = null,
    count = 0;
  for (let i = 0; i < nums.length; ++i) {
    if (!count) {
      candidate = nums[i];
    }
    count += candidate == nums[i] ? 1 : -1;
  }
  return candidate;
};

时间复杂度 O(n)

空间复杂度 O(1)

排序 + 取中间值

因为多数元素数目超过一半，所以排序后中间值肯定是多数元素

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  quickSort(nums, 0, nums.length - 1);
  return nums[Math.floor(nums.length / 2)];
};

function quickSort(A, p, r) {
  if (p < r) {
    let q = Partition(A, p, r);
    quickSort(A, p, q - 1);
    quickSort(A, q + 1, r);
  }
}

function Partition(A, p, r) {
  let x = A[r];
  let i = p - 1;
  for (let j = p; j < r; j++) {
    if (A[j] <= x) {
      i++;
      [A[i], A[j]] = [A[j], A[i]];
    }
  }
  [A[i + 1], A[r]] = [A[r], A[i + 1]];
  return i + 1;
}