寻找数组中出现一半以上的数字（Java）

寻找数组中出现一半以上的数字（Java） 寻找数组中出现一半以上的数字

（牛客网—牛客题霸算法篇—NC73）

题目描述

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

思路

Java实现
排序法
将数组进行排序，则出现次数超过一半的数字一定会出现在数组最中间，之后统计其出现的次数，判断是否超过一半。
时间复杂度：O(nlongn)
空间复杂度：O(1)
哈希法
定义一个新的数组用来存放每个数字出现的次数；
之后遍历数组，看是否有出现次数超过一半的数字。
时间复杂度：O(n)
空间复杂度：O(n)
候选人法
如果数组中存在众数，那么众数一定大于数组的长度的一半。
思想就是：如果两个数不相等，就消去这两个数。
最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。

代码实现

排序法

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        for(int i=0;iarray[j]){
                    int temp=array[i];
                    array[i]=array[j];
                    array[j]=temp;
                }
            }
        }
        int temp=array[array.length/2];
        int num=0;
        for(int i=0;iarray.length/2)
            return temp;
        return -1;
    }
}

哈希法

import java.util.HashMap;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null)
            return 0;
        if(array.length==1)
            return array[0];
        HashMap map=new HashMap();
        for(int i=0;i 
候选人法
 
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int number=-1;
        int num=0;
        for(int i=0;iarray.length/2)
            return number;
        return 0;
    }
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5605682.html