剑指Offer | 数组中出现次数超过一半的数字

阳光穿透心脏的1/2处 2022-05-23 03:15 157阅读 0赞

做了个剑指Offer的题目目录，链接如下：  
[https://blog.csdn.net/mengmengdastyle/article/details/80317246][https_blog.csdn.net_mengmengdastyle_article_details_80317246]

## 一、题目 ##

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

## 二、思路 ##

(1) Arrays.sort()用法。  
对一个数组的所有元素进行排序，并且是按从小到大的顺序。

import java.util.Arrays;
    
    public class Findshu {
    
        public static void main(String[] args) {
            int[] in = {
       7,4,5,3,3,6,4,2,4,5};
            Arrays.sort(in);
            for(int i =0;i<in.length;i++){          
                System.out.print(in[i] + " ");
            }
        }
    }

输出结果：2 3 3 4 4 4 5 5 6 7  
（2）  
1. 用Arrays.sort()先将数组进行排序；  
2. 然后选择中间的点array\[中间位置\]；  
3. new一个计数的，循环对比，如果和中间数相等则计数加一；  
4. 如果数的数小于总数的一半则返回0，多于一半则返回中间数；

## 三、代码 ##

import java.util.Arrays;
    public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
            //先分情况判断，将特殊情况处理掉
            int len = array.length;
            if(len < 1){
                return 0;
            }
            int count = 0;//计数
            Arrays.sort(array);//排序
            int mid = array[len/2];//取中间数
            //对比，如果和中间数相等则计一个 count+1
            for(int i=0;i<len;i++){
                if(mid == array[i]){
                    count++;
                }
            }
            //如果数的数小于总数的一半则返回0
            if(count <= (len/2)){
                mid = 0;
            }
            return mid;
        }
    }

[https_blog.csdn.net_mengmengdastyle_article_details_80317246]: https://blog.csdn.net/mengmengdastyle/article/details/80317246