首页 > itarticle > majority element

majority element

admin 11月 13, 2020 0

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

又是大神级别算法，O(n) time O(1) space fastest solution，比快排一遍找中位数还要快。。给跪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
public class  {
    public int majorityElement(int[] num) {
        int major=num[0], count = 1;
        for(int i=1; i<num.length;i++){
            if(count==0){
                count++;
                major=num[i];
            }else if(major==num[i]){
                count++;
            }else count--;
            
        }
        return major;
    }
}

顺便附上证明论文：

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

虽然我知道你们肯定没人看的。

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能