首页 > 其他 > 详细

Majority Element II

时间:2016-10-09 10:54:21      阅读:183      评论:0      收藏:0      [点我收藏+]

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

  1. How many majority elements could it possibly have?
  2. Do you have a better hint? Suggest it!
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {

        vector<int> res;
        int m = 0, n = 0, cm = 0, cn = 0;
        for (size_t i = 0; i < nums.size(); i++) {
            if (nums[i] == m)
                cm++;
            else if (nums[i] == n)
                cn++;
            else if (cm == 0) {
                m = nums[i];
                cm++;
            } else if (cn == 0) {
                n = nums[i];
                cn++;
            } else {
                cn--;
                cm--;
            }
        }

        cm = 0;
        cn = 0;
        for (auto num : nums) {
            if (num == m) {
                cm++;
            } else if (num == n) {
                cn++;
            }
        }
        if (cm > nums.size() / 3)
            res.push_back(m);
        if (cn > nums.size() / 3)
            res.push_back(n);
        return res;
    }
};

 

Majority Element II

原文:http://www.cnblogs.com/wxquare/p/5941260.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!