剑指offer - 数组中出现次数超过一半的数字(Java实现)

题目链接：https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&&tqId=11181&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：使用 Java 类库中的 HashMap 来记录每种数字出现的次数，如果超过了半数，则输出次数字，否则输出 0。

import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int ans = 0, n = array.length;
        Map<Integer, Integer> map = new HashMap<>();
        for(int val : array) {
            if(map.get(val) == null) map.put(val, 1);
            else map.put(val, map.get(val) + 1);
            if(map.get(val) > n / 2) {
                ans = val;
                break;
            }
        }
        return ans;
    }
}

import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int ans = 0, n = array.length;
        Map<Integer, Integer> map = new HashMap<>();
        for(int val : array) {
            if(map.get(val) == null) map.put(val, 1);
            else map.put(val, map.get(val) + 1);
        }
        Set<Integer> set = map.keySet();
        for(int key : set) {
            if(map.get(key) > n / 2) {
                ans = key;
                break;
            }
        }
        return ans;
    }
}

  思路二：使用 Arrays 中的 sort 函数对数组进行一个排序，如果存在众数，那么中最中间的那个数必定是众数，找到这个数字然后遍历数组记录其出现的次数，如果超过半数则输出该数字，否则输出 0。

import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int ans = 0, n = array.length;
        Map<Integer, Integer> map = new HashMap<>();
        for(int val : array) {
            if(map.get(val) == null) map.put(val, 1);
            else map.put(val, map.get(val) + 1);
        }
        Set<Integer> set = map.keySet();
        for(int key : set) {
            if(map.get(key) > n / 2) {
                ans = key;
                break;
            }
        }
        return ans;
    }
}

  思路三：在看题解的时候看到了这个思路，比较巧妙，首先我们设置一个哨兵，用来表示当前自己手中所持有的数字，同时记录这个数字出现的次数，在遍历的过程中会出现两种情况：

• 首先这个哨兵手中没有数字，那么此时我们就可以给他一个数字，并且记录当前他得到的这个数字的次数为 1
• 这个哨兵手中已经有了数字，如果此时的数字和哨兵手中的数字相同那么哨兵可以继续持有这个数字，并且增加其出现次数；如果此时数字和哨兵手中的数字不同，那么这个时候我们拿这个数字和哨兵手中的数字进行一个抵消，并且将哨兵手中的数字出现的次数减一。
    综上所述：如果存在众数，这个过程就相当于我们不断将两个不同的数字进行抵消，那么此时哨兵此时手中剩下的就是众数；如果不存在众数，那么哨兵手中的最后手中可以有数字，也可能没有数字。最后我们就统计哨兵手中数字的出现的次数，就可以判断是否存在众数，如果存在则输出该数字，否则删除该数字。

  import java.util.*;
  public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int ans = -1, cnt = 0, n = array.length;
        for(int i = 0; i < n; ++ i) {
            if(cnt == 0) { //哨兵手中有数字
                ans = array[i];
                ++ cnt;
            } else {//没有数字
                if(ans == array[i]) ++ cnt;//当前与持有的数字相同
                else -- cnt;//不相同
            }
        }
        cnt = 0;
        for(int i = 0; i < n; ++ i) {
            if(ans == array[i]) ++ cnt;
        }
        if(cnt <= n / 2) ans = 0;
        return ans;
    }
  }