LeetCode题解：169. 多数元素，分治，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/majority-element/

解题思路：

1. 出现次数大于 n/2 的元素，实际上就是数组中数量最多的元素。
2. 可以将数组分割为两段，选取每段中最多的元素，即为当前数组中最多的元素。
3. 利用递归将数组无限分割，并重复步骤2.

// 统计每个子数组中最多元素的数量
function countMax(nums, start, end, max) {
  let count = 0; // 用于计数

  // 根据start和end遍历子数组并计数
  for (let i = start; i <= end; i++) {
    nums[i] === max && count++;
  }

  return count;
}
function recursion(nums, start, end) {
  // 递归终止条件
  // 当start === end时，表示所选区间只有一个元素，即可作为最大元素返回
  if (start === end) {
    return nums[start];
  }

  // 当前层递归逻辑
  // 选取当前nums区间的中间索引，将区间拆分成两段
  const midIndex = start + Math.floor((end - start) / 2);

  // 下探到下一层递归
  // 获取两段子数组数量最多的元素
  const leftMax = recursion(nums, start, midIndex);
  const rightMax = recursion(nums, midIndex + 1, end);

  // 统计子数组数量最多元素的具体数量
  const leftCount = countMax(nums, start, end, leftMax);
  const rightCount = countMax(nums, start, end, rightMax);

  // 选取当前子数组中数量最多的元素
  // 注意此处是固定写法，假设只有3个元素，如[5,5,6]、[5,6,5]、[5,6,6]
  // 数组都会被分割为前两个元素和后一个元素两组
  // 此方法可以保证这些case都可以找到正确的元素
  return leftCount > rightCount ? leftMax : rightMax;
}
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  // 利用递归将数组不断切分成两段，并逐层对比两段中数量最多的元素，将其提供给上层做对比，最终得到结果
  return recursion(nums, 0, nums.length - 1);
};