剑指offer28.数组中出现次数超过一半的数字（Java）

题目描述

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

解题思路

思路一，利用排序的思想

将一组数排序，判断与中位数数值，相同数值的个数是否>n/2

思路二，计数器

将每个数字出现次数统计，求出次数>n/2的

思路三，消消乐

遍历数组，如果相邻两个元素不同，消去（当前个数-1）；相同，保留（当前个数+1）。
我们设想一下，如果数组中有一个数目超过一半的数number，那么经过我们的消消乐后，剩下的数字一定number。
但是，如果剩下了数字，不一定就是number，所以最终还需要判断一下。

知识点

Java中sort排序

1.数组升序

Arrays.sort(数组名)

2.集合排序

List<Integer> list = new ArrayList<Integer>(Arrays.asList(10, 3, 6, 1, 4, 5, 9));
Collections.sort(list);

hashmap

当前key是否存在

map.containsKey(key)

遍历hashmap

 for(Map.Entry<Integer,Integer> entry:map.entrySet()){
          entry.getValue();
          entry.getKey();           
}        

代码

排序法—Arrays.sort()(慢）

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        int i = array[array.length/2];
        int count=0;
        for(int n = 0;n<array.length;n++){
            if(array[n]==i)
                count++;
        }
        if(count>array.length/2)
            return i;
        else
            return 0;
        
    }
}

计数器法—HashMap

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //构造映射，数组值及其个数
        Map<Integer,Integer> map = new HashMap<>();
        
        //遍历数组并计数
        for(int i=0;i<array.length;i++){
            //map中有array[i]，将当前值+1
            if(map.containsKey(array[i])){
                int count = map.get(array[i]);
                map.put(array[i],count+1);
            }
            else
                map.put(array[i],1);                
        }
        
        //遍历map
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()> (array.length/2))
                return entry.getKey();           
        }        
        return 0;
    }
}

消消乐法

将其看作战争场面，多方人员混战
如果己方没人了，找到一个阵营投靠。
战场上遇到同伴，则己方人数+1
遇到敌人，需要己方成员与其同归于尽
最终，剩下的一定为同一阵营的人。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int last = -1;//当前剩下的值
        
        int count = 0;//计数器
        
        for(int i = 0;i<array.length;i++){
            //当前没有阵营，选择一个，last为己方阵营，count 为数量
            if(count==0){
                last = array[i];
                count++;
            }
            //如果是同伴，己方数量加1
            if(last == array[i]){
                count++;
            }
            //如果是敌人，己方数量-1（同归于尽）
            else
                count--;
        }
        //此时，剩下的last即为最终获胜者
        
        //确认最终获胜者阵营总人数是否满足题设
        count=0;
        for(int j=0;j<array.length;j++){
            if(array[j]==last){
                count++;}
        }
        
        if(count>array.length/2)
            return last;
        else
            return 0;   
    }
}