اڪثريت جو عنصر ليٽ ڪوڊ حل


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon ايپل Atlassian Bloomberg ڪريو ڏاڏي گوگل Microsoft جي Oracle سيڪشن Snapchat ياهو فائدا
تقسيم ۽ فتح هاشمي

مسئلي جو بيان

اسان کي هڪ ڏنو ويو آهي صف انٽيگرز جو اسان کي انٽيگر واپس ڪرڻ جي ضرورت آهي جيڪا صف ۾ ⌊N / 2⌋ کان وڌيڪ وقت ايندي آهي جتي ⌊ the منزل آپريٽر آهي. انهي عنصر کي اڪثريت جو عنصر سڏيو ويندو آهي. ياد رکجو ته ان پٽ صف ۾ هميشه اڪثريت جو عنصر شامل هوندو آهي.

مثال

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

تڪرار: اين اين / 2⌋ = 4/2 = 2. ۽ انٽيگر '3' صف ۾ 3 ڀيرا ٿئي ٿو.

Array = {1 , 1 , 2}
1

وضاحت: ⌊ اين / 2⌋ = ⌊3 / 2⌋ = 1. ۽ '1' صف ۾ 2 ڀيرا ٿئي ٿو.

رستو (هش ٽيبل)

اسان هر عنصر جي تعدد کي هاري ٽيبل ۾ صف ۾ محفوظ ڪري سگهون ٿا. ان کان پوء عدد معلوم ڪرڻ لاءِ آسان ٿي وڃي ٿو ته فریکوئنسي> ⌊N / 2⌋.

الورورٿم

  1. صف ۾ انٽيگرز جي تعدد کي ذخيرو ڪرڻ لاءِ هش ٽيبل کي شروع ڪريو. ات
  2. هر عنصر لاءِ ، iلسٽ ۾:
    • وڌايو فريڪئنسي [مان] يا سيٽ فريڪئنسي [i] = 0 جيڪڏهن اهو اڳ ۾ ئي ميز ۾ نه آهي
    •  If فريڪئنسي [مان] > ن / 2:
      • مون کي موٽ
  3. واپسي -1 (گڏ ڪرڻ واري غلطي کان بچڻ لاءِ)
  4. نتيجو ڇاپيو

اڪثريت جو عنصر ليٽ ڪوڊ حل جو لاڳو

سي ++ پروگرام

#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

اڪثريت عنصر ليٽ ڪوڊ حل جي پيچيدگي تجزيه

وقت جي پيچيدگي

اي (اين) جئين اسان اڪثريت جي عنصر کي ڳولڻ لاءِ صف کي گذري چڪا آهيون. N = صف جو قد.

خلائي پيچيدگي

اي (اين) جئين صف ۾ مختلف عنصرن جو وڌ کان وڌ تعداد ٿي سگهي ٿو: ن - ⌊ اين / 2⌋ جيئن ته اڪثريت جو عنصر گهٽ ۾ گهٽ قابض آهي ⌊ اين / 2⌋ انڊيڪس. ان ڪري ، خلا جي پيچيدگي ليڪ آهي.

پهچ (بوائر-مور ووٽنگ الورگيتم)

اهو مسئلو هڪ سٺو مثال آهي ته اسين عنصرن جي وهڪري ۾ اڪثريت عنصر کي ڪيئن ڳولي سگهنداسين. بائر-مور ووٽنگ الگورٿم اھو عنصر ڳولڻ لاءِ استعمال ڪيو ويندو آھي جيڪو ھڪڙي ترتيب ۾ ⌊N / 2⌋ جڳھن کان وڌيڪ جڳھ تي آھي. ھي الگورتھم ھڪڙي برقرار رکي ٿو اميدوار ۽ ان جي ڳڻپ صف ۾. اسان صف سان هڪڙو پاس پاس هلون ٿا اميدوار = -1 ۽ ڳڻپ = 0. جيڪڏھن صف ۾ ڪو عنصر آھي اميدوار، اسين وڌي رهيا آهيون ڳڻپ. ٻي صورت ۾ ، اسان ان کي گهٽائڻ وارا آهيون. جيڪڏهن شمار صفر ٿي وڃي ٿو ، اسان تبديل ڪريون ٿا اميدوار ۽ ان کي قائم ڪيو ڳڻپ 0 ڏانهن واپس

ان جي ڪمائي کي سمجھڻ جي لاءِ ، هيٺ ڏنل مثال تي عمل ڪريو.

اڪثريت جو عنصر ليٽ ڪوڊ حل

هي الگورٿٿم س theي عمل کي چونڊ سمجهي ٿو ۽ پهريان هڪ اميدوار مقرر ڪري ٿو. جيڪو سڀ کان وڌيڪ ووٽ حاصل ڪري ٿو اڪثريت اميدوار آهي. مٿين مثال ۾ ، اسين شروعات ۾ 1 جي طور تي اميدوار چونڊون ٿا ، پر جئين ته اسان صف ۾ انڊيڪس 4 تائين پهتا آهيون ، اسان مشاهدو ڪيون ٿا ڳڻپ = 0 ، جنهن جو مطلب آهي ته اسان ڪيترن ئي اميدوارن کي غير اميدوار طور ڏٺو آهي. تنهن ڪري ، اسان موجوده عنصر کي اميدوار چونڊيندا آهيون ۽ پروسيس کي جاري رکون ٿا. جئين اسان آهيون ضمانت ڪيل آهي صف ۾ اڪثريت وارو عنصر هجڻ لاءِ ، آخري اميدوار جيڪو اسان سان رهجي ويو آهي اڪثريت جو عنصر هوندو.

الورورٿم

  1. شروعاتي ٻه متغير: اميدوار ۽ cnt اميدوار کي ذخيرو ڪرڻ ۽ ان جي فرائض جي ترتيب متعلقہ اسٽوريشن لاءِ
  2. هاڻي ، هر عنصر لاءِ i صف ۾
    • If cnt صفر جي برابر آهي:
      • تازو اميدوار = آئون
    • If i جي برابر آهي اميدوار:
      • واڌارو cnt: سي ٽي ++
    • ٻئي:
      • گهٽجڻ cnt: سي ٽي–
  3. واپسي اميدوار
  4. نتيجو ڇاپيو

اڪثريت جو عنصر ليٽ ڪوڊ حل جو لاڳو

سي ++ پروگرام

#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

اڪثريت عنصر ليٽ ڪوڊ حل جي پيچيدگي تجزيه

وقت جي پيچيدگي

اي (اين) جئين اسان هڪ ڀيرو س arrayي صف کي پار ڪريون ٿا. هتي ، N = صف جو قد.

خلائي پيچيدگي

اي (1) جئين اسان مسلسل يادگيري جي جڳهه استعمال ڪندا آهيون.