数组中出现次数超过一半的数字

小咪咪 2022-12-28 00:59 265阅读 0赞

剑指Offer 39 数组中出现次数超过一半的数字 [easy]
在这里插入图片描述

一、题解1

1. 思路：hash字典
  1. hash 字典统计数量，数量大于数组长度一半时返回结果
2. 时间复杂度：O(n)
3. 空间复杂度：O(n)

二、题解2

1. 思路：排序
  1. 排序
  2. 排序后的中位数一定是的结果
2. 时间复杂度：O(nlogn)
3. 空间复杂度：O(logn) 排序递归栈空间
4. 实现
  1. /** * @param {number[]} nums * @return {number} */
  2. var majorityElement = function(nums) { 
  3.     nums.sort((a, b) => a - b);
  4.     return nums[Math.floor(nums.length / 2)];
  5. };

三、题解3

1. 思路：摩尔投票法（Boyer-Moore）
  1. 前提：目标数的数量大于数组长度的一半
  2. 每一个目标数与其他如何非目标数抵消，最终剩下的一定是目标数
2. 步骤

在这里插入图片描述

补充

  • 当votes变为0时，若上一轮假设的众数是目标数，则其他数与目标数消耗的数量一致，剩下的数字中目标数数量依旧大于一半
  • 若上一轮假设的众不是目标数，则目标数消耗数量小于其他数，剩下的数字中目标数数量依旧大于一半
3. 时间复杂度：O(n)
4. 空间复杂度：O(1)
5. 实现
  1. /** * @param {number[]} nums * @return {number} */
  2. var majorityElement = function(nums) { 
  3.     // 预处理（无）
  5.     // 摩尔投票法
  6.     let curr = nums[0], vote = 1;
  7.     for(let i=1, len=nums.length; i<len; i++){ 
  8.         if(vote === 0) curr = nums[i];
  9.         if(nums[i] === curr) vote++;
  10.         else vote--;
  11.     }
  13.     // 返回
  14.     return curr;
  15. };

四、题解4

1. 思路：位运算
  1. 目标数数量大于数组长度的一半，相应的，该目标数的二进制数中，每一位(1 / 0)的数量也大于数组长度的一半

发表评论

表情：
评论列表 （有 0 条评论，265人围观）

还没有评论，来说两句吧...

相关阅读