کوچکترین عنصر دقیقاً K بار تکرار شد


سطح دشواری متوسط
اغلب در بلزابار رسانه کوملی نتسکوپ کارت گرافیک Nvidia اپرا ServiceNow UHG Optum
صف مخلوط رشته

به ما آرایه A [] در اندازه n داده می شود. ما باید کوچکترین عنصری را پیدا کنیم که دقیقاً k بار در صف.

مثال

ورودی

A [] = {1 ، 2 ، 2 ، 5 ، 5 ، 2 ، 5}

K = 3

تولید

کوچکترین عنصر با فرکانس K: 2

رویکرد 1: نیروی بی رحم

ایده اصلی

برای هر عنصر در آرایه ، می توانیم فرکانس آن را با عبور از کل آرایه پیدا کنیم و اگر فرکانس آن برابر با K باشد ، حداقل پاسخ قبلی و این عنصر را خواهیم گرفت. در پایان ، پاسخ نهایی خود را چاپ خواهیم کرد.

الگوریتمی برای یافتن کوچکترین عنصر دقیقاً K بار تکرار شده

  1. یک متغیر 'flag' را با false شروع کنید. اگر هر عنصری با فرکانس K پیدا کرده ایم یا نه نشان می دهد.
  2. یک حلقه برای I در محدوده 0 تا n-1 اجرا کنید
    1. تعداد متغیر را با صفر مقداردهی کنید که فرکانس A [i] را در آرایه محاسبه کند.
    2. یک حلقه برای j در محدوده 0 تا n-1 اجرا کنید
      1. اگر A [j] برابر با A [i] باشد ، تعداد را 1 افزایش دهید.
    3. اگر شمارش برابر با K است ، ans = min را به روز کنید (ans ، A [i]).
  3. اگر پرچم درست است ، آن ها را چاپ کنید ، در غیر اینصورت هیچ عنصری با فرکانس K چاپ نکنید.

پیاده سازی

برنامه C ++

#include <bits/stdc++.h>
using namespace std;
void smallestElementRepeatedExactlyKTimes(vector<int> A, int K)
{
    int n = A.size();
    bool flag = false;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int count = 0;
        for (int j = 0; j < n; j++)
        {
            if (A[i] == A[j])
            {
                count++;
            }
        }
        if (count == K)
        {
            if (flag == false)
            {
                flag = true;
                ans = A[i];
            }
            else
            {
                ans = min(ans, A[i]);
            }
        }
    }
    if (flag == false)
    {
        cout << "There is no element with frequency K.";
    }
    else
    {
        cout << "Smallest element with frequency K is: " << ans;
    }
    return;
}
int main()
{
    vector<int> A = {1, 2, 2, 5, 5, 2, 5};
    int K = 3;
    smallestElementRepeatedExactlyKTimes(A, K);
    return 0;
}
Smallest element with frequency K is: 2

برنامه JAVA

public class Main
{
    static void smallestElementRepeatedExactlyKTimes(int A[],int K)
    {
        int n = A.length;
        boolean flag = false;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int count = 0;
            for (int j = 0; j < n; j++)
            {
                if (A[i] == A[j])
                {
                    count++;
                }
            }
            if (count == K)
            {
                if (flag == false)
                {
                    flag = true;
                    ans = A[i];
                }
                else
                {
                    ans = Math.min(ans, A[i]);
                }
            }
        }
        if (flag == false)
        {
            System.out.print("There is no element with frequency K.");
        }
        else
        {
            System.out.print("Smallest element with frequency K is: "+ ans);
        }
        return;
    }
  public static void main(String[] args) {
    int A[] = {1, 2, 2, 5, 5, 2, 5};
        int K = 3;
        smallestElementRepeatedExactlyKTimes(A, K);
  }
}
Smallest element with frequency K is: 2

تجزیه و تحلیل پیچیدگی برای یافتن کوچکترین عنصر دقیقاً K بار تکرار شده

پیچیدگی زمانی

ما از دو حلقه تو در تو استفاده می کنیم ، هر دو به اندازه N. بنابراین کل پیچیدگی زمان است O (N ^ 2).

پیچیدگی فضا

ما از فضای ثابت استفاده می کنیم. بنابراین پیچیدگی فضا است O (1).

رویکرد 2: استفاده از هش کردن

ایده اصلی

ما می توانیم فرکانس هر عنصر را در یک جدول هش ذخیره کنیم.

پس از آن ، ما فقط می توانیم جدول هش را رد کنیم و کوچکترین عنصر با فرکانس دقیق K را پیدا کنیم.

الگوریتمی برای یافتن کوچکترین عنصر دقیقاً K بار تکرار شده

  1. اگر هر عنصر در جدول هش باشد ، فرکانس را ذخیره کنید.
  2. یک متغیر 'flag' را با false شروع کنید. اگر هر عنصری با فرکانس K پیدا کرده ایم یا نه نشان می دهد.
  3. جدول هش را تکرار کنید و کوچکترین عنصر را با فرکانس K پیدا کنید.
  4. اگر پرچم درست است ، ans را چاپ کنید ، در غیر این صورت هیچ عنصری با فرکانس K چاپ نکنید.

با مثال درک کنید

A [] = {1 ، 2 ، 2 ، 5 ، 5 ، 2 ، 5}

K = 3

برای این آرایه ، جدول هش به شکل زیر خواهد بود:

کوچکترین عنصر دقیقاً K بار تکرار شد

پیاده سازی

برنامه C ++

#include <bits/stdc++.h>
using namespace std;
void smallestElementRepeatedExactlyKTimes(vector<int> A, int K)
{
    int n = A.size();
    bool flag = false;
    int ans = 0;
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (auto element : hash_table)
    {
        if (element.second == K)
        {
            if (flag == false)
            {
                flag = true;
                ans = element.first;
            }
            else
            {
                ans = min(ans, element.first);
            }
        }
    }
    if (flag == false)
    {
        cout << "There is no element with frequency K.";
    }
    else
    {
        cout << "Smallest element with frequency K is: " << ans;
    }
    return;
}
int main()
{
    vector<int> A = {1, 2, 2, 5, 5, 2, 5};
    int K = 3;
    smallestElementRepeatedExactlyKTimes(A, K);
    return 0;
}
Smallest element with frequency K is: 2

برنامه JAVA

import java.util.*; 
public class Main
{
    static void smallestElementRepeatedExactlyKTimes(int A[],int K)
    {
        int n = A.length;
        boolean flag = false;
        int ans = 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(Map.Entry element: hash_table.entrySet())
        {
            if(((int)element.getValue()==K))
            {
                if(flag==false)
                {
                    flag=true;
                    ans=((int)(element.getKey()));
                }
                else{
                    ans=Math.min(ans,((int)(element.getKey())));
                }
            }
        }
        if (flag == false)
        {
            System.out.print("There is no element with frequency K.");
        }
        else
        {
            System.out.print("Smallest element with frequency K is: "+ ans);
        }
        return;
    }
  public static void main(String[] args) {
    int A[] = {1, 2, 2, 5, 5, 2, 5};
        int K = 3;
        smallestElementRepeatedExactlyKTimes(A, K);
  }
}
Smallest element with frequency K is: 2

تجزیه و تحلیل پیچیدگی برای یافتن کوچکترین عنصر دقیقاً K بار تکرار شده

پیچیدگی زمانی

ما فقط یک بار آرایه را رد می کنیم ، بنابراین پیچیدگی زمان مناسب است بر).

پیچیدگی فضا

ما یک جدول هش برای ذخیره فرکانس عناصر در آرایه حفظ می کنیم تا پیچیدگی فضا باشد بر).

منابع