229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

难度:medium

题目:给定一整数数组,找出其元素出现次数大于其三分之一长度的所有元素。

注意:算法时间复杂度O(n),空间复杂度为O(1)

思路:投票法。

1 找出三个不同的候选人,各消除一票,如果票数为0 退出候选人队列。

2 最后对剩下的候选人重新统计票数

Runtime: 2 ms, faster than 97.44% of Java online submissions for Majority Element II.

Memory Usage: 39.8 MB, less than 29.68% of Java online submissions for Majority Element II.

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (null == nums) {
            return result;
        }
        
        int[] elems = new int[2];
        int[] count = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (elems[0] == nums[i]) {
                count[0]++;
            } else if (elems[1] == nums[i]) {
                count[1]++;
            } else {
                if (count[0] > 0 && count[1] > 0) {
                    count[0]--;
                    count[1]--;
                } else if (0 == count[0]) {
                    elems[0] = nums[i];
                    count[0] = 1;
                } else if (0 == count[1]) {
                    elems[1] = nums[i];
                    count[1] = 1;
                }
            }
        }
        int c0 = 0, c1 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count[0] > 0 && nums[i] == elems[0]) {
                c0++;
            }
            if (count[1] > 0 && nums[i] == elems[1]) {
                c1++;
            }
        }
        
        if (c0 > nums.length / 3) {
            result.add(elems[0]);
        }
        
        if (c1 > nums.length / 3) {
            result.add(elems[1]);
        }
        
        return result;
    }
}

原文 

https://segmentfault.com/a/1190000018325444

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 229. Majority Element II

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址