写点什么

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

用户头像
Lee Chen
关注
发布于: 2020 年 11 月 25 日
LeetCode题解:169. 多数元素,分治,JavaScript,详细注释

原题链接: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);
};
复制代码


发布于: 2020 年 11 月 25 日阅读数: 46
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:169. 多数元素,分治,JavaScript,详细注释