Majority Element II

Description

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Solution(javascript)

/* eslint-disable no-loop-func */


/** 初步的思考：等于 n/3 的情况最多能有 3 个, 多余 n/3 的情况最多有两个
 * 所以两轮遍历即可以找到结果
 * 又因为 x > n/3 所以只要满足  x - (n - x) > - 3/n 即可
 * https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html
 * 摩尔投票
 * @param {number[]} nums
 * @return {number[]}
 */
// const majorityElement = function (nums) {
//   const map = {}
//   const length = () => Object.keys(map).length
//   // 可能的 candidate
//   for (const num of nums) {
//     if (!map[num]) {
//       if (length() < 2) {
//         map[num] = 1
//       } else {
//         Object.keys(map).forEach((key) => {
//           map[key] -= 1
//           if (map[key] === 0) {
//             delete map[key]
//           }
//         })
//       }
//     } else {
//       map[num] += 1
//     }
//   }
//   const check = x => nums.reduce(
//     (acc, n) => {
//       if (n === x) {
//         acc += 1
//       }
//       return acc
//     }, 0,
//   ) > nums.length / 3
//   return Object.keys(map).map(x => Number(x)).filter(check)
// }

/** Quick Select
 * https://leetcode.com/problems/majority-element-ii/discuss/63542/Quick-Select-C%2B%2B-Solution
 * @param {number[]} nums
 * @return {number[]}
 */
const majorityElement = function (nums) {
  const swap = (i, j) => {
    const temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
  }
  const length = nums.length / 3
  const result = []
  const sort = (lo, hi) => {
    if (lo >= hi) {
      if (hi - lo + 1 > length) {
        result.push(nums[lo])
      }
      return
    }
    let i = lo
    const v = nums[lo]
    let lt = lo
    let gt = hi
    while (i <= gt) {
      if (nums[i] < v) {
        swap(i, lt)
        i++
        lt++
      } else if (nums[i] > v) {
        swap(i, gt)
        gt--
      } else {
        i++
      }
    }
    if (gt - lt + 1 > length) {
      result.push(nums[gt])
    }
    if (lt - lo > length) {
      sort(lo, lt - 1)
    }
    if (hi - gt > length) {
      sort(gt + 1, hi)
    }
  }
  sort(0, nums.length - 1)
  return result
}