اکثریت عنصر لیٹ کوڈ حل  


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون ایپل اٹلی بلومبرگ فیس بک گودادی گوگل مائیکروسافٹ اوریکل سیکشن Snapchat یاہو غذائیت
یلگوردمز کوڈنگ تقسیم اور فتح ہیکنگ انٹرویو انٹرویو کی تیاری لیٹ کوڈ LeetCodeSolutions۔

مسئلہ یہ بیان  

ہمیں ایک دیا جاتا ہے صف عدد کا ہمیں انٹیجر واپس کرنا ہوگا جو صف میں ⌊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' صف میں 2 بار واقع ہوتی ہے۔

نقطہ نظر (ہیش ٹیبل)  

ہم ہر عنصر کی تعدد کو ہیش ٹیبل میں سرنی میں اسٹور کرسکتے ہیں۔ پھر تعدد> ⌊N / 2⌋ رکھنے والے عدد کی جانچ کرنا آسان ہوجاتا ہے۔

الگورتھم

  1. صف میں عدد کی تعدد کو ذخیرہ کرنے کے لئے ہیش ٹیبل کا آغاز کریں: فریکوئنسی
  2. ہر عنصر کے لئے ، i، صف میں:
    • اضافہ تعدد [i] یا سیٹ کریں تعدد [i] = 0 اگر یہ پہلے سے ٹیبل میں نہیں ہے
    •  If تعدد [i] > N / 2:
      • واپس i
  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

اکثریت عنصر لیٹ کوڈ حل کی پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) جیسا کہ ہم اکثریت عنصر تلاش کرنے کے لئے ایک بار صف کو عبور کرتے ہیں۔ N = سرنی کا سائز۔

یہ بھی دیکھتے ہیں
انوگرام لیٹ کوڈ کے دو حل تیار کرنے کے لئے کم از کم اقدامات کی

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

O (N) چونکہ صف میں الگ الگ عناصر کی زیادہ سے زیادہ تعداد ہوسکتی ہے۔ N - ⌊N / 2⌋ چونکہ اکثریت عنصر میں کم از کم قبضہ ہوتا ہے /N / 2⌋ اشارے لہذا ، خلائی پیچیدگی لکیری ہے۔

نقطہ نظر (بوئیر مور ووٹنگ الگورتھم 

یہ مسئلہ اس کی عمدہ مثال ہے کہ ہم عناصر کے دھارے میں اکثریت کا عنصر کیسے پاسکتے ہیں۔ بائیر مور ووٹنگ الگورتھم ایک عنصر کو تلاش کرنے کے لئے استعمال ہوتا ہے جو ایک ترتیب میں ⌊N / 2⌋ سے زیادہ مقامات پر قبضہ کرتا ہے۔ یہ الگورتھم برقرار رکھتا ہے a امیدوار اور اس کی شمار صف میں۔ ہم صف کے ایک پاس کو چلاتے ہیں امیدوار = -1 اور شمار = 0. اگر صف میں کوئی عنصر ہے امیدوار، ہم اضافہ شمار. ورنہ ، ہم اس میں کمی کرتے ہیں۔ اگر گنتی صفر ہوجائے تو ، ہم اس کو تبدیل کریں امیدوار اور اس کی ترتیب دیں شمار 0 پر واپس

اس کے کام کو سمجھنے کے لئے ، ذیل میں دی گئی مثال کی پیروی کریں:

اکثریت عنصر لیٹ کوڈ حل

یہ الگورتھم عمل کو ایک انتخاب سمجھتا ہے اور پہلے کسی امیدوار کا فیصلہ کرتا ہے۔ جس کو سب سے زیادہ ووٹ ملتے ہیں وہ اکثریت کا امیدوار ہوتا ہے۔ مذکورہ بالا مثال میں ، ہم ابتدائی طور پر ایک امیدوار کا انتخاب 1 کرتے ہیں ، لیکن جیسے ہی ہم صف میں اشاریہ 4 پر پہنچتے ہیں ، ہم مشاہدہ کرتے ہیں کہ گنتی = 0 ، جس کا مطلب ہے کہ ہم نے غیر امیدوار جتنے امیدوار دیکھے ہیں۔ لہذا ، ہم موجودہ عنصر کو بطور امیدوار منتخب کرتے ہیں اور عمل جاری رکھتے ہیں۔ چونکہ ہم ہیں بات کی ضمانت صف میں اکثریت کا عنصر رکھنے کے لئے ، آخری امیدوار جس کے ساتھ ہم رہ گئے ہیں وہ اکثریت کا عنصر ہوگا۔

الگورتھم

  1. دو متغیرات کو شروع کریں: امیدوار اور cnt امیدوار اور اس کی تعدد متعلقہ تکرارات کے لئے ذخیرہ کرنے کے لئے
  2. اب ، ہر عنصر کے لئے i صف میں:
    • If cnt صفر کے برابر ہے:
      • : اپ ڈیٹ امیدوار = i
    • If i مساوی ہے امیدوار:
      • اضافہ cnt: cnt ++
    • اور:
      • کمی 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

اکثریت عنصر لیٹ کوڈ حل کی پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) جیسا کہ ہم ایک بار پوری صف کو عبور کرتے ہیں۔ یہاں ، N = سرنی کا سائز۔

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

O (1) چونکہ ہم مستقل میموری کی جگہ استعمال کرتے ہیں۔