Java练习题第八期：求数组中超过数组长度一半的数字

差点忘了今天是国庆节，先祝大家国庆快乐~
今日分享的第二道题，希望能对你们有帮助！

前言

如果又哪里写错了或者理解错了，希望大佬指出！谢谢！

一，题目

【数组中出现次数超过一半的数字】
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
数据范围：n<=50000 ，数组中元素的值:0<=val<=10000
要求：空间复杂度： O(1)，时间复杂度:O(n)

二，解题思路

1，思路一

先排序，再找到中间的数字X，最后再次遍历这个数组，看X出现了多少次，也就是检验X是否就是出现次数超过数组一半的那个数。

2，思路二

整体思路：如果两个数不相等，就消去这个数，在最坏情况下，每次消去一个众数和一个非众数，如果众数存在的情况下，最后剩下的那个数就一定是众数。（如下图）

三，代码

代码1：

import java.util.Arrays;

public class Main4 {
    public int  MoreThanHalfNum_Solution(int[] array){
        if(array==null||array.length==0){
            return 0;
        }
        Arrays.sort(array);
        int len = array.length;
        int midNum = array[len/2];
        int count=0;
        for (int i = 0; i < len; i++) {
            if(array[i]==midNum){
                count++;
            }
        }
        if(count>len/2){
            return midNum;
        }
        return 0;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

代码2：

public class Main5 {
    public int  MoreThanHalfNum_Solution(int[] array) {
        if (array==null||array.length==0){
            return 0;
        }
        int result = array[0];
        int times = 1;
        int len = array.length;
        for (int i = 0; i <len ; i++) {
            if (times!=0){
                if(array[i]==result){
                    ++times;
                }else {
                    --times;
                }
            }else {
                result = array[i];
                times = 1;
            }
        }
        for (int i = 0; i < len; i++) {
            if (array[i]==(len/2)){
                times++;
            }
        }
        if(times>len/2){
            return result;
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

好了，以上就是本期的练习题分享，希望对你们有帮助，如果有哪个地方不懂的，可以私信我哈！
下期再见啦~