寻找出现次数过半的元素

给定一个整数数组,求数组中出现次数超过数组长度一半的元素。
要求:时间复杂度为O(n)
输入、输出描述
输入:
arr: 非空整数数组
输出:
数组中出现次数超过数组长度一半的元素
Example
输入:
arr=[1,2,2,3,2]
输出:
2
代码:
import java.util.*;

public class Main {

 

 public int solution(int[] arr,int n) {
        int x = 0, votes = 0;
        for(int num : arr){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }

}
一个创业中的苦逼程序员
评论专区

隐藏