多數元素II Leetcode解決方案


難度級別
經常問 土磚 亞馬遜 蘋果 彭博社 Facebook 谷歌 Microsoft微軟 Zenefits
排列

在這個問題上,我們得到了一個 排列 整數目的是找到所有發生在 ⌊N/3⌋ 數組中的時間,其中N =數組的大小,⌊是下位運算符。 我們需要返回此類元素的數組。

元素範圍: -10 ^ 9 10 9 ^

Array = {1 , 2 , 3 , 3 , 2}
2 3

解釋⌊N/3⌋=⌊5/3⌋=1。現在,整數2和3的頻率等於2,大於1。所以,我們打印它們。

Array = {1 , 2 , 3 , 4}
No majority elements

說明: 在這種情況下,我們找不到任何頻率大於1的元素。 因此,我們打印“無多數元素”。

方法(存儲頻率)

如標題所示,我們可以使用哈希表存儲數組中每個元素的頻率,然後檢查頻率大於 ⌊N/3⌋。 這樣,我們可以找到所有滿足條件的元素。

算法

  1. 初始化HashMap-頻率 存儲數組中元素的頻率以及列表/向量 導致 存儲大多數元素
  2. 對於每個元素 在數組中:
    • 增加其頻率: 頻率[i] ++(或如果尚未存在,則設置為1)
  3. 每一個 關鍵 在哈希圖中:
    1. If 頻率[關鍵] > N / 3
      1. 將其添加到 導致
  4. 返回清單 導致

多數元素II Leetcode解決方案的實現

C ++程序

#include <bits/stdc++.h>
using namespace std;

vector<int> majorityElement(vector<int>& a)
{
    int N = a.size();
    vector <int> result;
    unordered_map <int , int> frequency;
    for(int &x : a)
        frequency[x]++;
    for(auto &x : frequency)
        if(x.second > N / 3)
            result.emplace_back(x.first);
    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 3 , 3 , 2};
    vector <int> result = majorityElement(a);
    if(result.empty())
        cout << "No majority elements\n";
    else
        for(int &x : result)
            cout << x << " ";
    return 0;
}

Java程序

import java.util.*;

class majority_element_ii
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 3 , 3 , 2};
        List <Integer> result = majorityElement(a);
        if(result.size() == 0)
            System.out.println("No majority elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> majorityElement(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashMap <Integer , Integer> frequency = new HashMap <>();

        for(int i = 0 ; i < a.length ; i++)
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);

        for(Map.Entry i : frequency.entrySet())
        {
            Integer value = (int)i.getValue() , key = (int)i.getKey();
            if((int)value > ((a.length) / 3))
                result.add(key);
        }
        return result;
    }
}
2 3

多數元素II Leetcode解決方案的複雜性分析

時間複雜度

上) 當我們遍歷整個陣列一次以更新頻率時。 N =數組的大小。

空間複雜度

上) 因為我們使用哈希表來存儲頻率。

方法(Boyer-Moore投票算法)

首先要注意的是,最多可以有2個元素,其頻率大於 數組中的“ N / 3”。 因此,此問題與 多數元素 問題與 2 這次的多數元素。

我們已經使用Boyer-Moore的投票算法解決了多數元素問題。 在單個多數元素的情況下,我們可以通過比較當前元素是否為候選元素來使用該算法。 但是,在這種情況下,我們需要持有兩個潛在多數元素並並行更新其計數器。 借助這種直覺,我們可以將條件設置如下:

  • 設置數組中元素範圍之外的任意兩個候選元素。
  • 如果元素等於任一候選元素,則增加其計數器。
  • 如果一位候選人的計數器等於 0 在任何時候,我們都將當前元素設置為候選元素 if 當前元素不是其他候選元素。
  • 如果當前元素不等於任何一個候選者,我們將減少兩個候選者的計數器。

這樣,我們將繼續在數組中並行維護兩個不同的候選對象,而第一個候選對像不會影響另一個候選對象。 但是,我們最終得到的候選者可能不是真正的多數元素({1}就是這樣的一個例子)。 因此,有必要進行第二遍計算以計算最終得到的候選頻率。 基於此,我們可以返回多數元素的向量。

算法

  1. 初始化 坎迪燭光 存儲兩個候選者及其頻率 一號通cntXNUMX as 0.
  2. 對於每個元素 在數組中:
    • If candOne ==我:
      • 一號通++
    • 否則,如果 兩個 == i
      • cntXNUMX++
    • 否則,如果cntOne == 0
      • 分配 i as 坎迪: candOne =我
      • 將其計數設置為1: cntOne = 1
    • 否則,如果 cntTwo == 0
      • candTwo =我
      • cntTwo = 1
    • 兩位候選人的遞減計數:
      • cntOne –
      • cntTwo –
  3. 第二遍將其計數重新設置為零: cntOne = 0cntTwo = 0
  4. 對於數組中的每個元素:
    • 如果等於candOne:
      • cntOne ++
    • 否則等於candTwo:
      • cntTwo ++
  5. 初始化列表/向量 導致 存儲多數元素
  6. 如果cntOne> N / 3
    • 坎迪導致
  7. 如果cntTwo> N / 3
    • 兩個導致
  8. 打印結果

插圖:

多數元素II Leetcode解決方案

多數元素II Leetcode解決方案的實現

C ++程序

#include <bits/stdc++.h>
using namespace std;

vector <int> majorityElement(vector <int> &a)
{
    vector <int> result;
    int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
    for(int &i : a)
    {
        if(candOne == i)
            cntOne++;
        else if(candTwo == i)
            cntTwo++;
        else if(cntOne == 0)
        {
            candOne = i;
            cntOne++;
        }
        else if(cntTwo == 0)
        {
            candTwo = i;
            cntTwo++;
        }
        else
        {
            cntOne--;
            cntTwo--;
        }
    }

    cntOne = 0;
    cntTwo = 0;
    for(int &i : a)
    {
        if(i == candOne)
            cntOne++;
        if(i == candTwo)
            cntTwo++;
    }

    if(cntOne > ((int)a.size()) / 3)
        result.push_back(candOne);
    if(cntTwo > ((int)a.size()) / 3)
        result.push_back(candTwo);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 3 , 3 , 2};
    vector <int> result = majorityElement(a);
    if(result.empty())
        cout << "No majority elements\n";
    else
        for(int &x : result)
            cout << x << " ";
    return 0;
}

Java程序

import java.util.*;

class majority_element_ii
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 3 , 3 , 2};
        List <Integer> result = majorityElement(a);
        if(result.size() == 0)
            System.out.println("No majority elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> majorityElement(int[] a)
    {
        List <Integer> result = new ArrayList<>();

        int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
        for(int i : a)
        {
            if(candOne == i)
                cntOne++;
            else if(candTwo == i)
                cntTwo++;
            else if(cntOne == 0)
            {
                candOne = i;
                cntOne++;
            }
            else if(cntTwo == 0)
            {
                candTwo = i;
                cntTwo++;
            }
            else
            {
                cntOne--;
                cntTwo--;
            }
        }

        cntOne = 0;
        cntTwo = 0;
        for(int i : a)
        {
            if(i == candOne)
                cntOne++;
            if(i == candTwo)
                cntTwo++;
        }

        if(cntOne > (a.length) / 3)
            result.add(candOne);
        if(cntTwo > (a.length) / 3)
            result.add(candTwo);

        return result;
    }
}
3 2

多數元素II Leetcode解決方案的複雜性分析

時間複雜度

上) 當我們運行數組的兩次遍歷時,無論輸入如何。 N =數組的大小。

空間複雜度

O(1) 因為我們不斷的存儲空間。