程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode] Majority Element II

[LeetCode] Majority Element II

編輯:關於C++

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.

解題思路

摩爾投票法。投票法的核心是找出兩個候選眾數進行投票,需要兩遍遍歷,第一遍歷找出兩個候選眾數,第二遍遍歷重新投票驗證這兩個候選眾數是否為眾數即可。

實現代碼

C++:

class Solution {
public:
    vector majorityElement(vector& nums) {
        vector res;
        int m = 0, n = 0, cm = 0, cn = 0;
        for (int 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 = 1;
            }
            else if (cn == 0)
            {
                n = nums[i];
                cn = 1;
            }
            else
            {
                --cm;
                --cn;
            }
        }

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

        return res;
    }
};

Java:

public class Solution {
    public List majorityElement(int[] nums) {
        List res = new ArrayList();
        int m = 0, n = 0, cm = 0, cn = 0;
        for (int a : nums) {
            if (a == m) {
                ++cm;
            } else if (a == n) {
                ++cn;
            } else if (cm == 0) {
                m = a;
                cm = 1;
            } else if (cn == 0) {
                n = a;
                cn = 1;
            } else {
                --cm;
                --cn;
            }
        }

        cm = cn = 0;
        for (int a : nums){
            if (a == m) {
                ++cm;
            } else if (a == n) {
                ++cn;
            }
        }

        if (cm > nums.length / 3) {
            res.add(m);
        }
        if (cn > nums.length / 3) {
            res.add(n);
        }

        return res;
    }
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved