Majority Element II

今天是一到有關(guān)數(shù)學(xué)計(jì)算的題目，是Majority Element（回復(fù)016查看）的深入，來自LeetCode，難度為Medium，Acceptance為23.6%。

題目如下

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.

解題思路及代碼見閱讀原文

回復(fù)0000查看更多題目

思路如下

首先，在Majority Element一題中，我們要找出現(xiàn)次數(shù)多于一半的數(shù)，那么這樣的數(shù)字只有1個(gè)。在本題中，要找大于三分之一的數(shù)字，那么這樣的數(shù)最多有2個(gè)。

然后，我們知道了有2個(gè)數(shù)字之后，就可以用2個(gè)變量記錄兩個(gè)出現(xiàn)次數(shù)最多的數(shù)字。這個(gè)方法和Majority Element類似。

最后，遍歷整個(gè)數(shù)組，看這2個(gè)數(shù)的出現(xiàn)次數(shù)是否都多于三分之一。

代碼如下

java版

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        if(null == nums)
            return list;

        int num1 = 0, num2 = 0;
        int count1 = 0, count2 = 0;
        for(int i : nums) {
            if(count1 == 0 || num1 == i) {
                num1 = i;
                count1++;
            } else if(count2 == 0 || num2 == i) {
                num2 = i;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for(int i : nums) {
            if(i == num1)
                count1++;
            else if(i == num2)
                count2++;
        }
        if(count1 > nums.length / 3)
            list.add(num1);
        if(count2 > nums.length / 3)
            list.add(num2);
        return list;
    }
}

c++版

vector<int> majorityElement(vector<int>& nums) {
    int cnt1=0, cnt2=0;
    int a,b;

    for(int n: nums){
        if (cnt1 == 0 || n == a){
            cnt1++;
            a = n;
        }
        else if (cnt2 == 0 || n==b){
            cnt2++;
            b = n;
        }
        else{
            cnt1--;
            cnt2--;
        }
    }

    cnt1=cnt2=0;
    for(int n: nums){
        if (n==a)   cnt1++;
        else if (n==b) cnt2++;
    }

    vector<int> result;
    if (cnt1 > nums.size()/3)   result.push_back(a);
    if (cnt2 > nums.size()/3)   result.push_back(b);
    return result;
}

關(guān)注我
該公眾號(hào)會(huì)每天推送常見面試題，包括解題思路是代碼，希望對(duì)找工作的同學(xué)有所幫助

image