LeetCode169. 多数元素 (JavaScript解法)

169. 多数元素

题解

思路1：摩尔投票法

• 思路 由于数的数量超过一半，所以那个数的出现的频率,一定大于等于50%，如果res为正确的众数，则voted的数量不可能为0，所以最后的res就是众数。
• 分析时间复杂度O( N )空间复杂度 O( 1 )
• 代码实现

var majorityElement = function (nums) {
	// 初始化备选人和票数
	let res = nums[0] , voted = 0;
	  for(let n of nums) {
	    // 如果票数变成0则说明不是正确的候选人，更新候选人
	    if(voted === 0 ) res = n;
	    // 相等票数加一
	    if(res === n) voted++;
	    // 不相等则减一
	    else voted--;
	  }
	  return res
	};

思路2：分治

• 思路 : 把数字分为两部分，分别求出左右部分的众数，通过比较两边众数的出现的数量，来作为合并以后区间的众数，递归直到区间长度为1，则返回那个唯一的数。
• 分析时间复杂度O( N log N )空间复杂度 O( log N )
• 代码实现

var majorityElement = function (nums) {
	// 计算ele在对应的区间出现的次数
	const count = (left, right, nums, ele) => {
	    let count = 0;
	    for (let i = left; i <= right; i++) if (nums[i] === ele) count++;
	    return count
	  }
  // 找出对应区间的出现的众数
  const dfs = (nums, left, right) => {
 	// recursion terminator 
    if (left === right) return nums[left];
    // process current problem
    // 把当前区域分为两部分，并且进行分治
    let mid = Math.floor((right - left) / 2) + left;
    // 找出各个区域的众数
    let numsLeft = dfs(nums, left, mid);
    let numsRight = dfs(nums, mid + 1, right);
    // merge
    // 根据左右区间的众数出现的次数，作为当前区域的众数
    let res =  count(left, mid, nums, numsLeft) > count(mid + 1, right, nums, numsRight) ? numsLeft : numsRight;
    // return 
    return res
  }
  return dfs(nums, 0, nums.length - 1);
};

最后

以上就是危机发卡为你收集整理的LeetCode169. 多数元素 (JavaScript解法)的全部内容，希望文章能够帮你解决LeetCode169. 多数元素 (JavaScript解法)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。