ac

给定一个整型数组arr，请打印其中出现次数大于一半的数，如果没有这样的数，请输出-1

时间复杂度O(n),额外空间复杂度O(1)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            int val = sc.nextInt();
            arr[i] = val;
        }
        int ans = getHalf(arr);
        // print 结果
        System.out.println(ans);
    }

    static int getHalf(int[] arr){
        if(arr == null){
            return -1;
        }
        // 每次去掉2个数字
        int cnt = 0;
        int val = -1;
        for(int i=0; i<arr.length; i++){
            if(cnt == 0){
                cnt = 1;
                val = arr[i];
            }else if(arr[i] == val){
                cnt++;
            }else {
               cnt --;
            }
        }
        if(val != -1) {
            cnt = 0;
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == val){
                    cnt ++;
                }
            }
            if(cnt <= arr.length / 2){
                val = -1;
            }
        }
        return val;
    }

}
/*
4
2 2 3 3

-1

5
11 7 5 7 7

7
*/