اکثر عناصر II راه حل کد


سطح دشواری متوسط
اغلب در خشت آمازون سیب بلومبرگ فیس بوک گوگل مایکروسافت Zenefits
صف

در این مشکل ، به ما داده می شود صف از اعداد صحیح هدف یافتن همه عناصری است که بیش از حد اتفاق می افتند ⌊N / 3⌋ زمان در آرایه که در آن N = اندازه آرایه و ⌊ operator عملگر طبقه است. ما باید آرایه ای از این عناصر را برگردانیم.

محدوده عناصر: -10 ^ 9 به 10 ^ 9

مثال

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

توضیحNowN / 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. برای هر کلید در hashtap:
    1. If فرکانس [کلید] > N / 3
      1. آن را به نتیجه
  4. لیست را برگردانید نتیجه

پیاده سازی راه حل کد اکثریت عنصر II

برنامه 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;
}

برنامه جاوا

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 راه حل کد

پیچیدگی زمان

بر) همانطور که یکبار کل آرایه را مرور می کنیم تا فرکانس ها را به روز کنیم. N = اندازه آرایه.

پیچیدگی فضا

بر) همانطور که برای ذخیره فرکانس ها از یک جدول هش استفاده می کنیم.

رویکرد(الگوریتم رأی گیری بویر مور)

اولین چیزی که در اینجا باید توجه کرد این است که حداکثر 2 عنصر می تواند با فرکانس بیشتر از وجود داشته باشد ⌊N / 3⌋ در آرایه. بنابراین ، این مشکل همان مشکل است عنصر اکثریت مشکل با 2 این بار عناصر اکثریت.

ما قبلاً با استفاده از الگوریتم رأی گیری بویر مور مسئله Majority Element را حل کرده ایم. در مورد یک عنصر اکثریت منفرد ، می توانیم با مقایسه اینکه آیا عنصر فعلی کاندیدا است یا نه ، از الگوریتم استفاده کنیم. اما ، در این حالت ، ما باید دو عنصر اکثریت بالقوه را نگه داریم و شمارنده های آنها را به طور موازی به روز کنیم. با کمک این شهود می توانیم شرایط خود را به صورت زیر تنظیم کنیم:

  • هر دو نامزد تصادفی را خارج از محدوده عناصر آرایه تنظیم کنید.
  • اگر عنصر برابر با هر یک از نامزدها باشد ، شمارنده آن را افزایش دهید.
  • اگر شمارنده یک کاندیدا برابر باشد 0 در هر مرحله ، عنصر فعلی را به عنوان نامزد تعیین می کنیم if این عنصر فعلی نامزد دیگر نیست.
  • اگر عنصر فعلی با هر یک از نامزدها برابر نباشد ، شمارنده هر دو نامزد را کاهش می دهیم.

به این ترتیب ، ما دو نامزد مختلف را به طور موازی در آرایه حفظ می کنیم بدون اینکه نامزد اول بر دیگری تأثیر بگذارد. با این حال ، این احتمال وجود دارد که نامزدهایی که در آخر به آنها می رسیم ، عناصر اکثریت واقعی نیستند ({1 ، 1 ، 2 ، 2 ، 3 ، 3} یکی از این نمونه هاست). بنابراین ، لازم است که یک گذرگاه دوم را برای شمارش فرکانس نامزدهای انتخاباتی انجام دهیم. بر این اساس ، ما می توانیم بردار عناصر اکثریت را برگردانیم.

الگوریتم

  1. شروع کردن candOne و candtwo برای ذخیره این دو نامزد و فرکانس های آنها cntOne و cntTwo as 0.
  2. برای هر عنصر در آرایه:
    • If candOne == من:
      • cntOne++
    • دیگر اگر candTwo == i
      • cntTwo++
    • دیگر اگر cn باشدtOne == 0
      • اختصاص دادن i as candOne: candOne = من
      • تعداد آن را به عنوان 1 تنظیم کنید: cntOne = 1
    • دیگر اگر cntTwo == 0
      • candTwo = من
      • cntTwo = 1
    • شمارش تقلیل هر دو نامزد:
      • cntOne–
      • cntTwo–
  3. برای پاس دوم تعداد آنها را صفر کنید: cntOne = 0 و cntTwo = 0
  4. برای هر عنصر در آرایه:
    • اگر برابر با candOne باشد:
      • cntOne ++
    • اگر برابر با candTwo باشد ، دیگری:
      • cntTwo ++
  5. لیست / بردار را آغاز کنید نتیجه برای ذخیره عناصر اکثریت
  6. اگر cntOne> N / 3 باشد
    • فشار candOne به نتیجه
  7. اگر cntTwo> N / 3 باشد
    • فشار candTwo به نتیجه
  8. نتیجه را چاپ کنید

تصویر:

اکثر عناصر II راه حل کد

پیاده سازی راه حل کد اکثریت عنصر II

برنامه 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;
}

برنامه جاوا

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 راه حل کد

پیچیدگی زمان

بر) همانطور که دو پاس از آرایه را صرف نظر از ورودی اجرا می کنیم. N = اندازه آرایه.

پیچیدگی فضا

O (1) همانطور که فضای حافظه ثابت داریم