169. Majority Element

2020-05-21

原题：169. Majority Element

解法一

思路：brute force，循环嵌套依次找出每个元素出现的次数；
时间复杂度：O(n^2)

解法二

思路：用map计数，找出出现次数>长度一半的元素
时间复杂度：O(n)

// Runtime: 120 ms, faster than 5.64% of JavaScript online submissions for Majority Element.
// Memory Usage: 38.1 MB, less than 21.43% of JavaScript online submissions for Majority Element.
var majorityElement = function (nums) {
  const map = {};
  for (let num of nums) {
    map[num] = (map[num] || 0) + 1;
    if (map[num] >= nums.length / 2) {
      return num;
    }
  }

  //题干保证众数一定存在
};

解法三

思路：先把数组排序，众数一定在中间的位置
时间复杂度：O(n*logn)

// Runtime: 84 ms, faster than 10.46% of JavaScript online submissions for Majority Element.
// Memory Usage: 37.5 MB, less than 57.14% of JavaScript online submissions for Majority Element.
var majorityElement = function (nums) {
  nums.sort();
  return nums[~~(nums.length / 2)];
};

解法四

思路：分治。把数组一分为二，找出前半段的众数以及众数出现的次数（lm, lc），后半段的众数以及众数出现的次数（rm, rc）。如果lm==lc，则众数为lm；否则比较lc和rc，返回较大的对应lm/rm。
时间复杂度：O(logn+n)

var majorityElement = function (nums, start = 0, end) {
  const findNumCount = function (num, start, end) {
    let count = 0;
    for (let i = start; i <= end; i++) {
      if (nums[i] == num) {
        count++;
      }
    }
    return count;
  };
  const helper = function (start, end) {
    if (end - start == 0) {
      return [nums[start], 1];
    }

    const midIndex = ~~((start + end) / 2);
    const [lm, lc] = helper(start, midIndex);
    const [rm, rc] = helper(midIndex + 1, end);
    if (lm == rm) {
      return [lm, lc + rc];
    } else {
      return lc > rc
        ? [lm, lc + findNumCount(lm, midIndex + 1, end)]
        : [rm, rc + findNumCount(rm, start, midIndex)];
    }
  };

  return helper(0, nums.length - 1)[0];
};

Test Cases:

test("test1", () => {
  expect(majorityElement([3, 2, 3])).toEqual(3);
});

test("test2", () => {
  expect(majorityElement([2, 2, 1, 1, 1, 2, 2])).toEqual(2);
});

test("test3", () => {
  expect(
    majorityElement([
      345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345, 543, 345
    ])
  ).toEqual(345);
});