【剑指 offer】39. 数组中出现次数超过一半的数字

本节目录

刷前点说

以后的话，除了代码和想说的话，就会的剪短文章的长度，

因为在写文章上浪费了太多的是时间！

其实刷题是不难的，难的是坚持！

这个分栏是《剑指 offer》 的经典题目，

并在这个博客里记录自己的理解与学习过程！

题目介绍(LINK)

那关于题目的话，我就不做过多的介绍了，照抄的意义不大，我在这里直接贴链接了！

LeetCode链接：点击这里！

NowCoder链接：点击这里！

思路/想法

1. 初始思路/最终思路

思路一：Map

定义map，使用 <数字，次数> 的映射关系，最后统计每个字符出现的次数；

这个方法的空间复杂度比较大！

思路二：排序

排序，出现次数最多的数字，一定在中间位置。

然后检测中间出现的数字出现的次数是否符合要求，比较简单！

思路三：删除

这个思路你可以看作是巧妙优化后的代码！

目标数据超过数组长度的一半，那么对数组，我们同时去掉两个不同的数字，到最后剩下的一个数就是该数字！

上面的逻辑晦涩难懂:

解释一下：设置一个初始值（数组的第一个元素），然后和后面的值比较，相同计数器

++

，不同就

--

后把初始值换成下一个数组的值。

概念就是，比较不一样就“删除”，那剩下的值就是最多的！

这个删除不是真正意义上的删除，而是不拿它比较了！

如果剩下两个，那么这两个也是一样的，就是结果，在其基础上把最后剩下的一个数字或者两个回到原来数组中，将数组遍历一遍统计一下数字出现次数进行最终判断。

如果你还不理解，就看我写的代码，看了代码不会你直接在评论里喊我或者是私信我，我直接大视频给你讲！

2. 注意点

在OJ的时候JAVA用的是JDK1.8，但是没有添加import相关的包，需要自己导入；

C++不用写头文件，它是默认已经添加过的！

代码实现

1. 定义Map实现代码

importjava.util.Map;importjava.util.HashMap;publicclassSolution{publicintMoreThanHalfNum_Solution(int[] array){if(array ==null|| array.length ==0){return0;}Map<Integer,Integer> map =newHashMap<>();for(int i =0; i < array.length; i++){if(map.containsKey(array[i])){int count = map.get(array[i]);
                count++;
                map.put(array[i], count);// 找到了，次数+1}else{
                map.put(array[i],1);// 找不到并记录次数为1}if(map.get(array[i])> array.length /2){// 验证次数return array[i];}}return0;}}

2. 排序实现

importjava.util.Map;classSolution{publicintmajorityElement(int[] array){if(array ==null|| array.length ==0){return0;}Arrays.sort(array);// 首先排序数组然后找次数int target = array[array.length /2];int count =0;// 计数器for(int i =0; i < array.length; i++){if(target == array[i]){
                count++;}}if(count > array.length /2){return target;}return0;}}

3. 对比删除法

classSolution{publicintmajorityElement(int[] array){if(array ==null|| array.length ==0){return0;}int target = array[0];//设定初始目标值int times =1;//出现次数for(int i =1; i < array.length; i++){if(times ==0){
                target = array[i];
                times =1;}elseif(target == array[i]){
                times++;}else{
                times--;}}
        
        times =0;for(int j =0; j < array.length; j++){if(target == array[j]){
                times++;}}return times >(array.length /2)? target :0;}}

感谢语

面试的时候你回答了思路一和思二的解法，面试官觉得你还可以，但是还是不够的！

比较之下，第三个方法是比较有意思的！

对于第二个方法：

其实笔试的时候直接写就可以了，就是用现成的（库里的排序方法），因为快！

但是，在面试的时候，你可以和面试官沟通：

你可以问面试官你是想看我排序的能力还是想看其他的能力！

最后感谢大家的阅读！