[剑指offer题解][Java]数组中出现次数超过一半的数字

太过爱你忘了你带给我的痛 2022-02-17 12:30 144阅读 0赞

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

# 前言 #

最近看了好多数据结构文章，但是数据结构拾遗系列迟迟憋不出，主要原因是很多数据结构其实非常偏门，不仅日常很难遇到，学起来还涉及很多数学模型，很难有快速的理解方法。

本着女排“短平快”的精神，先更新下剑指offer题解系列。

众所周知，《剑指offer》是一本“好书”。

为什么这么说？因为在面试老鸟眼里，它里面罗列的算法题在面试中出现的频率是非常非常高的。有多高，以我目前不多的面试来看，在所有遇到的算法体中，本书算法题出现的概率大概是60%，也就是10道题有6题是书中原题，如果把变种题目算上，那么这个出现概率能到达90%。

如果你是个算法菜鸡（和我一样），那么最推荐的是先把剑指offer的题目搞明白。

对于剑指offer题解这个系列，我的写作思路是，对于看过文章的读者，能够做到：

*  迅速了解该题常见解答思路（偏门思路不包括在内，节省大家时间，实在有研究需求的人可以查阅其它资料）
 *  思路尽量贴近原书（例如书中提到的面试官经常会要求不改变原数组，或者有空间限制等，尽量体现在代码中，保证读者可以不漏掉书中细节）
 *  尽量精简话语，避免冗长解释
 *  给出代码可运行，注释齐全，关注细节问题

# 题目介绍 #

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

# 解题思路 #

## 方法一 ##

### 思路 ###

该方法改变了原数组。

首先要得到一个推论，那就是一旦有数字大于数组的一半，那么排序后的数组的中位数肯定是这个数字，那么我们就先找出这个数字。

这种算法是受快速排序算法的启发。在随机快速排序算法中，我们现在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组的中位数。如果它的下标大于n/2，那么中位数应该位于它的左边，我们可以接着在它的左边部分的数组中查找。如果它的下标小于n/2，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程

找到这个数字后，再判断他是否符合条件（大于数组的一半），因为很有可能他是数组中出现次数最多的，但是未必大于数组的一半。

详细细节见代码注释。

### 代码 ###

public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
            if(array.length<=0) {
                return 0;
            }
    
            int start = 0;
            int length = array.length;
            int end  = length-1;
            // 右移1位，相当于除2，效率更高
            int middle = length>>1;
            // 当前位置
            int index = Partition(array,start,end);
    
            // 直到取到中位数，才是结果
            while(index!=middle){
                if(index>middle){
                    index = Partition(array,start,index-1);
                }
                else{
                    index = Partition(array,index+1,end);
                }
            }
            int result = array[middle];
    
            // 需要统计该数字个数，必须要大于数组长度的一半才能算
            int times = 0;
            for(int i=0;i<length;i++){
                if(result==array[i]){
                    times++;
                }
            }
            if(times*2 <= length){
                result = 0;
            }
            return result;
        }
    
        // 快排中的每次排序实现，返回的是交换后start位置，也就是index一直改变的位置
        private int Partition(int[] array,int start,int end){
            // 取平均值不一定是整数，所以必须除2取整，不能右移
            int flag = (array[start]+array[end])/2;
    
            while(start<end){
                while(array[end]>flag){
                    end--;
                }
                swap(array,start,end);
                while(array[start]<=flag){
                    start++;
                }
                swap(array,start,end);
            }
            return start;
        }
        private void swap(int[] array, int num1, int num2){
            int temp = array[num1];
            array[num1] = array[num2];
            array[num2] = temp;
        }
    }

## 方法二：两两消除 ##

### 思路 ###

该方法不改变原数组。

如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。  
在遍历数组时保存两个值：

*  times：次数
 *  result：当前数字

遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。

遍历结束后，所保存的数字即为所求。

之后，还要再判断它是否符合大于数组的一半。

详细细节见代码注释。

### 代码 ###

public int MoreThanHalfNum_Solution(int [] array) {
        int length = array.length;
        
        // 检测数组是否为空
        if (length == 0){
            return 0;
        }
        
        // 初始化result和times参数
        int result = array[0];
        int times = 1;
        
        //遍历数组（由于初始化过，所以直接从第二个数字开始）
        for(int i=1;i<length;i++){
            // 次数为0时写入下一个数字并将次数置1
            if(times == 0){
                result = array[i];
                times = 1;
            }
            // 数字相同，加1
            else if(array[i] == result){
                times++;
            }
            // 数字不同，减1
            else{
                times--;
            }
        }
        
        // 需要统计该数字个数，必须要大于数组长度的一半才能算
        times = 0;
        for(int i=0;i<length;i++){
            if(result==array[i]){
                times++;
            }
       }
        if(times*2 <= length){
           result = 0;
       }
        
       return result;
    }

## 方法三：hashmap ##

### 思路 ###

将数组中的数字依次遍历，并写入hashmap中，hashmap的值是该数字出现的次数，并在每次循环中判断是否该数次数大于数组的一半，若有直接返回数字，否则遍历完数组返回0。

### 代码 ###

思路简单，代码略。

# 总结 #

三种方法时间复杂度都是O（n）

# 关注我 #

我是一名后端开发。主要关注后端开发，数据安全，爬虫等方向。微信：yangzd1102

Github：[@qqxx6661][qqxx6661]

个人博客：

*  CSDN：[@qqxx6661][qqxx6661 1]
 *  知乎：[@Zhendong][Zhendong]
 *  简书：[@蛮三刀把刀][Link 1]
 *  掘金：[@蛮三刀把刀][Link 2]

### 原创博客主要内容 ###

*  Java知识点复习全手册
 *  Leetcode算法题解析
 *  剑指offer算法题解析
 *  SpringCloud菜鸟入门实战系列
 *  SpringBoot菜鸟入门实战系列
 *  Python爬虫相关技术文章
 *  后端开发相关技术文章

### 个人公众号：Rude3Knife ###

![个人公众号：Rude3Knife][Rude3Knife]

**如果文章对你有帮助，不妨收藏起来并转发给您的朋友们~**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxeHg2NjYx_size_16_color_FFFFFF_t_70]: /images/20220217/5d26781f9308476c83f85a3315a3ac67.png
[qqxx6661]: https://github.com/qqxx6661
[qqxx6661 1]: http://blog.csdn.net/qqxx6661
[Zhendong]: https://www.zhihu.com/people/yang-zhen-dong-1/
[Link 1]: https://www.jianshu.com/u/b5f225ca2376
[Link 2]: https://juejin.im/user/5b48015ce51d45191462ba55
[Rude3Knife]: /images/20220217/d87d968e32844c1c8ed4c1d147809462.png