JZ39 数组中出现次数超过一半的数字

JZ39 数组中出现次数超过一半的数字

数组中出现次数超过一半的数字_牛客题霸_牛客网 (nowcoder.com)

---

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

//11
//map
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++){
            if(map.containsKey(array[i])){
                map.put(array[i],(map.get(array[i])+1));
            }else{
                map.put(array[i],1);
            }
            if(map.get(array[i])>array.length/2){
                return array[i];
            }
        }
        return -1;
    }
}

// //众数非众数
// public class Solution {
//     public int MoreThanHalfNum_Solution(int[] array) {
//         int ret=array[0];
//         int times=1;
//         for(int i=1;i<array.length;i++){
//             if(times!=0){
//                 if(array[i]==ret){
//                     times++;
//                 }else{
//                     times--;
//                 }
//             }else{
//                 ret=array[i];
//                 times=1;
//             }
//         }
//         int count=0;
//         for(int i=0;i<array.length;i++){
//             if(array[i]==ret){
//                 count++;
//             }
//         }
//         return (count>array.length/2)?ret:-1;
//     }
// }