د اکثریت عنصر لیټکوډ حل


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon مڼه Atlassian د بلومبرګ فیسبوک GoDaddy د ګوګل د Microsoft سينه_پوښ کړی Snapchat د ياهو زینتونه
تقسیم او فتح ځورول

ستونزه بیان

موږ ته ورکړل شو سور د عددونو موږ اړتیا لرو چې عدد بیرته راسو چې په سر کې د ⌊N / 2⌋ وخت څخه ډیر پیښیږي چیرې چې floor the د پوړ چلوونکی دی. دې عنصر ته اکثریت عنصر ویل کیږي. په یاد ولرئ چې ان پټ صف کې تل اکثریت عنصر لري.

بېلګه

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

پراخه کیدل: ⌊N / 2⌋ = 4/2 = 2. او انټرجیر 3 3 په صف کې پیښ کیږي.

Array = {1 , 1 , 2}
1

تشریح: ⌊N / 2⌋ = ⌊3 / 2⌋ = 1. او '1' دوه ځله په صف کې واقع کیږي.

کړنلاره (د هشت ټبل)

موږ کولی شو په هر چاپ کې د هر عنصر فریکونسۍ په هش مېز کې وساتو. بیا دا اسانه کیږي چې د عدد تعدد> ⌊N / 2⌋ لرونکي انفرادي چک وګورئ.

الګوریتم

  1. په اشاره کې د انډیج د فریکونسۍ ساتلو لپاره د هش مېز پیل کړئ: د فریکونسي
  2. د هر عنصر لپاره ، i، په صف کې:
    • زیاتوالی فريکوينسي [i] یا ټاکل شوی فريکوينسي [i] = 0 که دا دمخه په میز کې نه وي
    •  If فريکوينسي [i] > N / 2:
      • بيرته راستنيدل
  3. بیرته راستنیدنه -1 (د تالیف غلطي څخه مخنیوی لپاره)
  4. پایله چاپ کړئ

د اکثریت عنصر لیټکوډ حل پلي کول

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;
}

جاوا پروګرام

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

د اکثریت عنصر لیټکوډ حل حل پیچلتیا تحلیل

د وخت پیچلتیا

O (N) لکه څنګه چې موږ د اکثریت عنصر موندلو لپاره یوځل صف ځنډوو. N = د صف اندازه.

د ځای پیچلتیا

O (N) لکه څنګه چې په صف کې د مختلف عناصرو اعظمي شمیر کیدی شي: N - ⌊N / 2⌋ لکه څنګه چې اکثریت عنصر لږترلږه نیسي ⌊N / 2⌋ شاخصونه له همدې امله ، د ځای پیچلتیا لیکه ده.

چلند (د بایر - مور رای ورکولو الګوریتم)

دا ستونزه یو ښه نثر دی چې څنګه موږ کولی شو د عناصرو په جریان کې اکثریت عنصر ومومو. د بایر - مور رای ورکولو الګوریتم د هغه عنصر موندلو لپاره کارول کیږي چې په ترتیب کې د ⌊N / 2⌋ څخه ډیر ځایونه نیسي. دا الګوریتم a ساتي کانديد او د هغې حساب په صف کې. موږ د سره د صف یوه برخه تیروو کانديد = -1 او حساب = 0. که په صف کې کوم عنصر وي کانديد، موږ وده کوو شمېرنه. نور ، موږ دا کمو. که چیرې شمیره صفر شي ، موږ بدل شو کانديد او تنظیم یې کړئ حساب بېرته 0 ته.

د دې په فعالیت پوهیدو لپاره لاندې مثال تعقیب کړئ:

د اکثریت عنصر لیټکوډ حل

دا الګوریتم پروسې د ټاکنو په توګه ګ considي او لومړی د کاندید په اړه پریکړه کوي. هغه څوک چې ډیری رایې ترلاسه کوي اکثریت نوماندان دی. په پورتني مثال کې ، موږ په پیل کې یو نوماند غوره کوو ، مګر لکه څنګه چې موږ په صف کې 1 شمیرو ته رسي ، نو موږ دا مشاهده کوو چې 4 = د کوم معنی چې موږ د غیر کاندیدانو په څیر ډیری نوماندان لیدلي دي. نو ، موږ اوسنی عنصر د نوماند په توګه غوره کوو او پروسې ته دوام ورکوو. ځکه چې موږ یو تضمين ترڅو په صف کې د اکثریت عنصر ولرو ، وروستی نوماندان چې موږ ورسره پاتې یو به اکثریت عنصر وي.

الګوریتم

  1. دوه تغیرات پیل کړئ: کانديد او CNT د اړوند تکرار لپاره کاندید او د دې فریکونسۍ ذخیره کول
  2. اوس ، د هر عنصر لپاره i په صف کې:
    • If CNT له صفر سره مساوي ده:
      • اوسمهال: کاندید = i
    • If i سره مساوي ده کانديد:
      • زياتوالی CNT: cnt ++
    • بل:
      • کمښت CNT: cnt–
  3. بیرته راګرځی کانديد
  4. پایله چاپ کړئ

د اکثریت عنصر لیټکوډ حل پلي کول

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;
}

جاوا پروګرام

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

د اکثریت عنصر لیټکوډ حل حل پیچلتیا تحلیل

د وخت پیچلتیا

O (N) لکه څنګه چې موږ یو ځل ټول صف راجمع کوو. دلته، N = د صف اندازه.

د ځای پیچلتیا

O (1) لکه څنګه چې موږ دوامداره حافظه ځای کاروو.