ایک صف میں K-th امتیازی عنصر  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل ByteDance ای بے Expedia فیس بک گوگل لنکڈ مائیکروسافٹ اوریکل Salesforce Spotify والمارٹ لیبز
تقسیم اور فتح ڈھیر

آپ کو پورا عدد دیا جاتا ہے صف A ، ایک صف میں K-th الگ عنصر کو پرنٹ کریں۔ دیئے جانے والے صف میں نقول شامل ہوسکتے ہیں اور آؤٹ پٹ میں صف کے تمام منفرد عناصر کے درمیان K-th الگ عنصر پرنٹ کرنا چاہئے۔ اگر k متعدد مختلف عناصر سے زیادہ ہے ، تو اس کی اطلاع دیں۔

مثال کے طور پر  

ان پٹ:

A [] = {3,4,4,1,2,3،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

K 2 =

: پیداوار

K ویں غیر اعادہ عنصر 2 ہے۔

وضاحت:

پہلا نان ریپیٹنگ عنصر 1 ہے ،

دوسرا غیر اعادہ عنصر 2 ہے۔

نقطہ نظر 1: بروٹ فورس  

مرکزی خیال

ہم گنتی متغیر کو برقرار رکھیں گے جو ہمیں پائے جانے والے غیر اعادہ عناصر کی تعداد کو محفوظ کرے گا۔ اب ہم تمام عناصر پر تکرار کریں گے اور ہر عنصر کے ل we ، ہم صف پر اعادہ کریں گے کہ یہ چیک کریں کہ آیا یہ کوئی اعادہ عنصر ہے یا نہیں ، اگر ایسا ہے تو پھر ہم گنتی کو 1 سے بڑھا دیں گے۔ K کے برابر ، ہم اس عنصر کو پرنٹ کریں گے۔

ایک صف میں K-th امتیازی عنصر کے لئے الگورتھم

  1. ایک متغیر کی گنتی کو صفر سے شروع کریں جو صف میں الگ الگ عناصر کی گنتی کرے گا۔
  2. I کے ل 0 1 سے n-XNUMX میں لوپ چلائیں
    1. جھنڈے کو جھوٹی کے ساتھ اعلان کریں جو سچ ہے اگر A [i] ایک اعادہ عنصر ہے اور اس کے برعکس ہے
    2. 0 سے n-1 تک کی حد میں j کے لئے لوپ چلائیں
      1. اگر میں برابر نہیں ہوں اور A [i] A [j] کے برابر ہوں تو ، جھنڈا = صحیح اور توڑ دیں
    3. اگر جھنڈا غلط ہے تو ، انکریمنٹ کی گنتی 1 کریں
    4. چیک کریں کہ اگر گنتی K کے برابر ہے تو ، A [i] پرنٹ کریں۔
  3. واپس
یہ بھی دیکھتے ہیں
2 متغیرات کا استعمال کرکے فبونیکی تسلسل پرنٹ کریں

عمل

C ++ پروگرام

#include <bits/stdc++.h>
using namespace std;
void kthDistinctElement(vector<int> &A, int k)
{
    int n = A.size();
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        bool flag = false;
        for (int j = 0; j < n; j++)
        {
            if (i != j and A[i] == A[j])
            {
                flag = true;
                break;
            }
        }
        if (!flag)
        {
            count++;
        }
        if (count == k)
        {
            cout << "K-th non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "K is greater than number of distinct element in the array." << endl;
    return;
}
int main()
{
    vector<int> A = {3, 4, 4, 1, 2, 3};
    int k = 2;
    kthDistinctElement(A, k);
    return 0;
}
K-th non-repeating element is: 2

جاوا پروگرام

public class Main
{
    static void kthDistinctElement(int A[], int k)
    {
        int n=A.length;
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            boolean flag = false;
            for (int j = 0; j < n; j++)
            {
                if (i != j && A[i] == A[j])
                {
                    flag = true;
                    break;
                }
            }
            if (!flag)
            {
                count++;
            }
            if (count == k)
            {
                System.out.println("K-th non-repeating element is: " + A[i]);
                return;
            }
        }
        System.out.println("K is greater than number of distinct element in the array.");
    }
  public static void main(String[] args) {
    int A[] = {3, 4, 4, 1, 2, 3};
        int k = 2;
        kthDistinctElement(A, k);
  }
}
K-th non-repeating element is: 2

کسی صف میں K-th ڈسٹ انکٹ عنصر کے لئے پیچیدگی کا تجزیہ

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

ہم دو گھونسلے والے لوپ ، دونوں سائز N کا استعمال کررہے ہیں۔ لہذا ، کل وقتی پیچیدگی ہے O (N ^ 2).

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

ہم کوئی اضافی جگہ استعمال نہیں کررہے ہیں ، لہذا جگہ کی پیچیدگی ہے O (1).

نقطہ نظر 2: ہیشنگ کا استعمال کرتے ہوئے  

مرکزی خیال

ہم سرنی کے ہر عنصر کی تعدد کو ہیش ٹیبل میں محفوظ کریں گے۔ اب ہم گنتی کے متغیر کو برقرار رکھیں گے جو ہمیں پائے جانے والے غیر اعادہ عناصر کی تعداد کو محفوظ کرے گا۔ اگلا ، ہم تمام عناصر پر تکرار کریں گے ، اور ہر عنصر کے ل، ، ہم جانچیں گے کہ آیا اس کی فریکوئنسی 1 سے زیادہ ہے یا نہیں ، اگر یہ 1 کے برابر ہے ، تو ہم گنتی میں 1 اضافہ کریں گے جس عنصر کے لئے گنتی بن جاتی ہے۔ K کے برابر ، ہم اس عنصر کو پرنٹ کریں گے۔

یہ بھی دیکھتے ہیں
سرکلر صف کا استعمال کرتے ہوئے Deque کا نفاذ

ایک صف میں K-th امتیازی عنصر کے لئے الگورتھم

  1. ہیش ٹیبل کا اعلان کریں جو سرنی کے ہر عنصر کی تعدد کو اسٹور کرے گا۔
  2. ایک متغیر کی گنتی کو صفر سے شروع کریں جو صف میں الگ الگ عناصر کی گنتی کرے گا۔
  3. I کے ل 0 1 سے n-XNUMX میں لوپ چلائیں
    1. اگر A [i] کی فریکوئینسی 1 ہے تو ، انکریمنٹ کی گنتی 1 کریں۔
    2. اگر گنتی K کے برابر ہے تو ، A [i] پرنٹ کریں۔
  4. واپس

مثال کے طور پر:

A [] = {3,4,4,1,2,3،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

K 2 =

ہیش ٹیبل اس طرح نظر آئے گی ،

ایک صف میں K-th امتیازی عنصرپن

عمل

C ++ پروگرام

#include <bits/stdc++.h>
using namespace std;
void kthDistinctElement(vector<int> &A, int k)
{
    int n = A.size();
    int count = 0;
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (hash_table[A[i]] == 1)
        {
            count++;
        }
        if (count == k)
        {
            cout << "K-th non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "K is greater than number of distinct element in the array." << endl;
    return;
}
int main()
{
    vector<int> A = {3, 4, 4, 1, 2, 3};
    int k = 2;
    kthDistinctElement(A, k);
    return 0;
}
K-th non-repeating element is: 2

جاوا پروگرام

import java.util.*; 
public class Main
{
    static void kthDistinctElement(int A[], int k)
    {
        int n=A.length;
        int count = 0;
        HashMap <Integer, Integer> hash_table = new HashMap<Integer, Integer> ();  
        for (int i = 0; i < n; i++)  
        { 
            if(hash_table.containsKey(A[i])) 
                hash_table.put(A[i], hash_table.get(A[i]) + 1); 
            else
                hash_table.put(A[i], 1); 
        } 
        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                count++;
            }
            if (count == k)
            {
                System.out.println("K-th non-repeating element is: " + A[i]);
                return;
            }
        }
        System.out.println("K is greater than number of distinct element in the array.");
    }
  public static void main(String[] args) {
    int A[] = {3, 4, 4, 1, 2, 3};
        int k = 2;
        kthDistinctElement(A, k);
  }
}
K-th non-repeating element is: 2

کسی صف میں K-th ڈسٹ انکٹ عنصر کے لئے پیچیدگی کا تجزیہ

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

ہم صرف دو بار صف پر اعادہ کر رہے ہیں۔ تو ، کل وقتی پیچیدگی ہے O (N).

یہ بھی دیکھتے ہیں
متعدد بار دہرانے والے عناصر میں سے کسی کو صرف پڑھنے والی صف میں تلاش کریں

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

ہم عناصر کی تعدد کو صف میں رکھنے کے لئے ہیش ٹیبل برقرار رکھے ہوئے ہیں۔ تو ، جگہ کی پیچیدگی ہے O (N).

حوالہ جات