Олонхийн элемент II Leetcode шийдэл


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Apple-ийн Bloomberg Facebook-ийн Google-ийн Microsoft- Зенефиц
Array

Энэ асуудалд бидэнд массив бүхэл тоонууд. Зорилго нь үүнээс илүү тохиолддог бүх элементүүдийг олох явдал юм ⌊N / 3⌋ массив дахь хугацаа = массивын хэмжээ ба ⌊ ⌋ нь шалны оператор юм. Бид ийм элементүүдийн массивыг буцааж өгөх хэрэгтэй.

Элементүүдийн хүрээ: -10 ^ 9 to 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-ээс их давтамжтай элемент олдсонгүй. Тиймээс бид “No Mostlyity elements” -ийг хэвлэж байна.

Хандалт (давтамж хадгалах)

Гарчгаас харахад хэш хүснэгт ашиглан массив дахь элемент бүрийн давтамжийг хадгалаад дараа нь давтамжаас их давтамжтай элементүүдийг шалгаж болно. ⌊N / 3⌋. Ийм байдлаар бид нөхцөлийг хангасан бүх элементүүдийг олж чадна.

Алгоритм

  1. HashMap эхлүүлэхдавтамж массив дахь элементийн давтамж, жагсаалт / векторыг хадгалах үр дүн дийлэнх элементүүдийг хадгалах
  2. Элемент бүрийн хувьд массивт:
    • Давтамжийг нэмэгдүүлэх: давтамж [i] ++ (эсвэл байхгүй бол 1 гэж тохируулсан)
  3. Бүх зүйлд гол hashmap дээр:
    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 шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) давтамжийг шинэчлэхийн тулд бүх массивыг нэг удаа туулахдаа. N = массивын хэмжээ.

Сансрын нарийн төвөгтэй байдал

O (N) бид давтамжийг хадгалахын тулд хэш хүснэгт ашигладаг.

Хандалт (Бойер-Мурын санал өгөх алгоритм)

Энд анзаарагдах хамгийн эхний зүйл бол хамгийн ихдээ 2-оос их давтамжтай элемент байж болно Массив дахь ⌊N / 3⌋. Тэгэхээр энэ асуудал яг адилхан болж байна Олонхийн элемент асуудалтай байна 2 Энэ удаад олонхийн элементүүд.

Бид Бойер-Мурын санал өгөх алгоритмыг ашиглан олонхын элементийн асуудлыг шийдсэн. Нэг олонхийн элементийн хувьд тухайн элемент нэр дэвшигч мөн эсэхийг харьцуулах замаар алгоритмыг ашиглаж болно. Гэхдээ энэ тохиолдолд бид олонхийн боломжит хоёр элементийг барьж, тоолуураа зэрэгцүүлэн шинэчлэх хэрэгтэй. Энэхүү зөн билгийн тусламжтайгаар бид нөхцөлөө дараахь байдлаар тохируулж болно.

  • Массивын элементүүдийн хүрээнээс гадуур хоёр санамсаргүй нэр дэвшигчийг тохируулна уу.
  • Хэрэв элемент нь нэр дэвшигчийн аль нэгтэй тэнцүү байвал түүний тоолуурыг өсгө.
  • Хэрэв нэг нэр дэвшигчийн тоолуур тэнцүү бол 0 ямар ч үед бид одоогийн элементийг нэр дэвшигчээр тохируулна if энэ одоогийн элемент нь бусад нэр дэвшигч биш юм.
  • Одоогийн элемент нь нэр дэвшигчдийн аль нэгтэй тэнцэхгүй бол бид хоёр нэр дэвшигчийн тоолуурыг бууруулдаг.

Ийм байдлаар бид эхний нэр дэвшигч нь нөгөөдөө нөлөөлөхгүйгээр массивын дагуу хоёр өөр нэр дэвшигчийг зэрэгцүүлэн хадгалсаар байна. Гэсэн хэдий ч, бидний нэр дэвшиж байгаа нэр дэвшигчид жинхэнэ олонхийн элемент биш байж магадгүй юм ({1, 1, 2, 2, 3, 3} нь ийм жишээ юм). Тиймээс бидний дуусдаг нэр дэвшигчдийн давтамжийг тоолохын тулд хоёр дахь дамжуулалтыг хийх шаардлагатай байна. Үүний үндсэн дээр бид олонхийн элементүүдийн векторыг буцааж өгч болно.

Алгоритм

  1. Эхлүүлэх candOne болон хоёр хоёр нэр дэвшигч ба тэдгээрийн давтамжийг хадгалах cntOne болон cntTwo as 0.
  2. Элемент бүрийн хувьд массивт:
    • If candOne == i:
      • cntOne++
    • өөр тохиолдолд candTwo == i
      • cntTwo++
    • өөр бол cntOne == 0
      • Даалгавар өг i as candOne: candOne = i
      • Түүний тоог 1 гэж тохируулна уу: cntOne = 1
    • өөр тохиолдолд cntTwo == 0
      • candTwo = i
      • cntTwo = 1
    • Хоёр нэр дэвшигчийн бууралтыг тоолох:
      • cntOne–
      • cntTwo–
  3. Хоёрдахь дамжуулалтанд тэдгээрийн тоог буцааж тэг болго. cntOne = 0 болон cntTwo = 0
  4. Массивын бүх элементүүдийн хувьд:
    • Хэрэв энэ нь candOne-тэй тэнцүү бол:
      • cntOne ++
    • Хэрэв энэ нь candTwo-тэй тэнцүү бол:
      • cntTwo ++
  5. Жагсаалт / вектор эхлүүлэх үр дүн олонхийн элементүүдийг хадгалах
  6. Хэрэв cntOne> N / 3
    • түлхэх candOne to үр дүн
  7. Хэрэв cntTwo> N / 3
    • түлхэх candTwo to үр дүн
  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 шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) бид оролтоос үл хамааран массивын хоёр дамжуулалтыг ажиллуулдаг. N = массивын хэмжээ.

Сансрын нарийн төвөгтэй байдал

O (1) Бид санах ойн тасралтгүй зайтай байдаг