Majority Element_查找数组中出现次数超过一半的元素

Sat May 16 12:44:45 CST 2015 665 算法

文章摘要来自LeetCode上的问题。给定一个数组,里面包含有一个出现次数超过数组大小一半的元素,求该元素。

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.


相信大家首先想到的方法就是先将数组排序,然后返回num[n/2]。因为既然该元素(majority)在数组里的出现次数超过数组大小n的二分之一(n/2),那么排序后的数组最中间的值必定是该元素(majority)。这样的解法,时间复杂度受限于采取何种排序算法,比如你用快速排序对数组进行排序,那么此问题的时间复杂度最好的情况下为O(nlogn).


那么有没有更好的方法呢?有,这个方法的时间复杂度为O(n),只需遍历一次数组。

从数组第一个数开始,假设其为最终需要返回的结果(majority)并记录它的出现次数count为1,若下一个数字与它相等则count++,若下一个数字与它不相等则count--;当count==0时则把当前值设为最终需要返回的结果(majority),那么一趟遍历过后majority保存的值就是正确的结果了。这种思路就相当于每一个元素与另一个不相同的元素一一对消了,对消完后剩下的元素必定是出现次数超过数组大小一半的元素。


以下是问题解法的Java实现:

public class Solution {
    public int majorityElement(int[] num) {
        if(num.length==0) return 0;
        int count = 1;
        int majority = num[0];
        for(int i = 1; i < num.length; i++){
            if(majority == num[i]){
                count++;
            } else {
                count--;
            }
            if(count == 0){
                majority = num[i];
                count=1;
            }
        }
        return majority;
    }
}



打赏
打赏

分享到: