多數元素Leetcode解決方案


難度級別 容易獎學金
經常問 亞馬遜 蘋果 Atlassian的 彭博社 Facebook GoDaddy的 谷歌 Microsoft微軟 神諭 部分 Snapchat 雅虎 Zenefits
分而治之 哈希

問題陳述

我們得到了一個 排列 整數我們需要返回在數組中出現的時間大於floorN /2⌋的整數,其中⌊⌊是下位運算符。 該元素稱為多數元素。 請注意,輸入數組始終包含一個多數元素。

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

排骨:⌊N/2⌋= 4/2 =2。並且整數'3'在數組中出現3次。

Array = {1 , 1 , 2}
1

解釋:⌊N/2⌋=⌊3/2⌋=1。'1'在數組中出現2次。

方法(哈希表)

我們可以在哈希表中存儲數組中每個元素的頻率。 這樣就很容易檢查頻率>⌊N/ 2 an的整數。

算法

  1. 初始化哈希表以將整數的頻率存儲在數組中: 頻率
  2. 對於每個元素, i,在數組中:
    • 增量 頻率[i] 或設置 頻率[i] = 0 如果它不在表中
    •  If 頻率[i] > N / 2:
      • 還給我
  3. 返回-1(以避免編譯錯誤)
  4. 打印結果

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

C ++程序

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

int majorityElement(vector <int> &a)
{
    int majorityCount = ((int) a.size()) / 2;
    unordered_map <int , int> frequency;
    for(int &i : a)
    {
        if(++frequency[i] > majorityCount)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

Java程序

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        HashMap <Integer , Integer> frequency = new HashMap<>();
        for(int i = 0 ; i < a.length ; i++)
        {
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);
            if(frequency.get(a[i]) > a.length / 2)
                return a[i];
        }
        return -1;
    }
}
2

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

時間複雜度

上) 當我們遍歷數組一次以找到多數元素時。 N =數組的大小。

空間複雜度

上) 因為數組中不同元素的最大數量可以是: N –⌊N/2⌋ 因為多數元素至少佔據 ⌊N/2⌋ 索引。 因此,空間複雜度是線性的。

方法(Boyer-Moore投票算法)

這個問題很好地說明瞭如何在元素流中找到多數元素。 Boyer-Moore投票算法用於查找序列中佔⌊N/2⌋個位置以上的元素。 該算法保持 候選人 在數組中。 我們使用 候選人 = -1和 =0。如果數組中的任何元素是 候選人,我們增加 算。 否則,我們將其遞減。 如果計數變為零,我們將 候選人 並設置它 回到0。

為了了解其功能,請按照以下示例操作:

多數元素Leetcode解決方案

該算法將流程視為選舉,然後首先確定候選人。 得票最多的人是多數候選人。 在上面的示例中,我們最初選擇一個候選對象為1,但是當我們到達數組中的索引4時,我們觀察到count = 0,這意味著我們看到的候選對象與非候選對像一樣多。 因此,我們選擇當前元素作為候選元素並繼續該過程。 既然我們是 保證 要在數組中具有多數元素,剩下的最後一個候選者將是多數元素。

算法

  1. 初始化兩個變量: 候選人 CNT 存儲相應迭代的候選者及其頻率
  2. 現在,對於每個元素 i 在數組中:
    • If CNT 等於零:
      • 更新: 候選人=我
    • If i 等於 候選人:
      • 增量 CNT: cnt ++
    • 別的:
      • 減量 CNT: cnt–
  3. 返回 候選人
  4. 打印結果

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

C ++程序

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

int majorityElement(vector <int> &a)
{
    int candidate = -1 , cnt = 0;
    for(int &i : a)
    {
        if(cnt == 0)
            candidate = i;
        cnt += (candidate == i) ? 1 : -1;
    }
    return candidate;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

Java程序

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        int candidate = -1 , cnt = 0;
        for(int i = 0 ; i < a.length ; i++)
        {
            if(cnt == 0)
                candidate = a[i];
            cnt += (candidate == a[i]) ? 1 : -1;
        }
        return candidate;
    }
}
2

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

時間複雜度

上) 當我們遍歷整個數組一次時。 這裡, N =數組的大小。

空間複雜度

O(1) 因為我們使用恆定的內存空間。