剑指Offer 39

忘是亡心i 2022-10-13 05:04 6阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]

### 原地数组 ###

时间复杂度空间复杂度较高

/** * @param {number[]} nums * @return {number} */
    var majorityElement = function(nums) { 
        let len = nums.length;
        let arr = Array(50000).fill(0);
        for(let i=0;i<len;i++){ 
            if(!arr[nums[i]]){ 
                arr[nums[i]]=1;
            }else{ 
                arr[nums[i]]++;
            }
        }
        let res = arr.findIndex((e)=>{ 
            return e>(len/2);
        })
        console.log(arr);
        return res;
    };

### 摩尔计票 ###

第一次听说的方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70 1]  
只需要一遍循环

//摩尔投票
    var majorityElement = function(nums) { 
        let ans = 0, count = 0;
        for(let i = 0; i < nums.length; i++){ 
            if(!count) {                 //若当前票数已经为0，则更换胜出者
                ans = nums[i];
                count++;
            }else count += nums[i] === ans ? 1 : -1; //若下一个相同+1，不同—1
        }
        return ans;
    };

时间复杂度On  
空间复杂度O1

从一道简单题中学到的新方法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]: /images/20221005/c66082fb53594530a3814db6d834ce7e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70 1]: /images/20221005/81045f7d0f174d09a90797d80906664f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，6人围观）

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

相关阅读

相关剑指offer：39-42记录

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例 1: 输入: \[1, 2, 3, 2,

墨蓝/ 2023年07月13日 04:10/ 0 赞/ 50 阅读

相关【LeetCode】《剑指Offer》第Ⅴ篇⊰⊰⊰ 39 - 47题

【LeetCode】《剑指Offer》第Ⅴ篇⊰⊰⊰ 39 - 47题文章目录【LeetCode】《剑指Offer》第Ⅴ篇⊰⊰⊰ 39 - 47题

逃离我推掉我的手/ 2022年11月04日 05:25/ 0 赞/ 4 阅读

相关剑指Offer 39

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

忘是亡心i/ 2022年10月13日 05:04/ 0 赞/ 7 阅读

相关剑指offer

剑指 offer 思路总结本部分主要是笔者在练习剑指 offer 时所做的笔记，如果出现错误，希望大家指出！题目 1. 二维数组中的查找题目：

布满荆棘的人生/ 2022年09月12日 15:56/ 0 赞/ 242 阅读

相关【剑指Offer】39平衡二叉树

题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。时间限制：1秒；空间限制：32768K；本题知识点：树解题思路需要用到查找二叉树深度的函数，根据平

绝地灬酷狼/ 2022年05月12日 13:42/ 0 赞/ 217 阅读

相关剑指offer-问题39

package offer; / offer interview 39 / public class Test39 {

旧城等待，/ 2022年05月11日 15:48/ 0 赞/ 177 阅读

相关剑指offer

[https://blog.csdn.net/u012193416/article/details/79253398][https_blog.csdn.net_u0121934

青旅半醒/ 2022年02月20日 16:21/ 0 赞/ 361 阅读

相关剑指offer

目录 1.二维数组中的查找 2.替换空格 3.从头到尾打印链表 4.重建二叉树 5.用两个栈实现队列 6.旋转数组的最小数字 7.斐

青旅半醒/ 2021年12月05日 03:27/ 0 赞/ 717 阅读

相关剑指offer

[剑指offer][offer] https://www.cnblogs.com/gzshan/p/10910831.html [offer]: https://sun

亦凉/ 2021年09月21日 01:12/ 0 赞/ 421 阅读

相关剑指offer

剑指offer Coding 1. 前言 2. 数组中重复的数字 2.1 找出数组中重复的数字 2.2 不修改数组找出重复的数字

ゞ浴缸里的玫瑰/ 2021年08月30日 13:19/ 0 赞/ 492 阅读