Хамгийн бага элемент яг K Times давтагдсан


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Белзабар Комли медиа Нетскоп Nvidia Opera ҮйлчилгээNow UHG Optum
Array Хаш String

Бидэнд n хэмжээтэй A [] массив өгөгдсөн болно. -Д яг k удаа давтагдсан хамгийн жижиг элементийг олох ёстой массив.

Жишээ нь

Оролт

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

K = 3

гаралтын

K давтамжтай хамгийн бага элемент нь: 2

Хандлага 1: Харгис хүч

Үндсэн санаа

Массивын бүх элементүүдийн хувьд бид массивыг бүхэлд нь туулж давтамжаа олох боломжтой бөгөөд хэрвээ түүний давтамж нь K-тэй тэнцүү бол бид хамгийн багадаа өмнөх хариулт болон энэ элементийг авах болно. Эцэст нь бид эцсийн хариултаа хэвлэх болно.

Яг K Times давтагдсан хамгийн бага элементийг олох алгоритм

  1. "Туг" гэсэн хувьсагчийг хуурамчаар эхлүүлнэ. Хэрэв бид K давтамжтай элемент олсон бол тугийг тэмдэглэнэ.
  2. 0-ээс n-1 хүртэлх мужид зориулж гогцоо ажиллуулна уу
    1. Массив дахь A [i] давтамжийг тоолох хувьсах тооллыг тэгээр эхлүүлнэ.
    2. 0-ээс n-1 хүртэлх j-ийн давталтыг ажиллуулна уу
      1. Хэрэв A [j] нь A [i] -тэй тэнцүү бол 1-ээр нэмэгдүүлнэ.
    3. Хэрэв тоо нь K-тэй тэнцүү бол ans = min (ans, A [i]) -ийг шинэчил.
  3. Шалгана уу, Хэрэв туг үнэн бол ans-ийг хэвлэ, эс бөгөөс 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 Times давтагдсан хамгийн бага элементийг олох алгоритм

  1. Хэрэв элемент бүрийг хэш хүснэгтэд байрлуулсан бол давтамжийг хадгална.
  2. "Туг" гэсэн хувьсагчийг хуурамчаар эхлүүлнэ. Хэрэв бид K давтамжтай элемент олсон бол тугийг тэмдэглэнэ.
  3. Хэш хүснэгтийг давтаж, K давтамжтай хамгийн бага элементийг олоорой.
  4. Хэрэв туг үнэн бол ans-ийг хэвлэ, эс тэгвээс K давтамжтай элемент байхгүй гэдгийг хэвлэ.

Үлгэр жишээгээр ойлгоорой

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

K = 3

Энэ массивын хувьд хэш хүснэгт дараах байдалтай байна.

Хамгийн бага элемент яг K Times давтагдсан

Хэрэгжүүлэх

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 удаа давтаж олох нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Бид массивыг зөвхөн нэг удаа туулж байгаа тул цаг хугацааны нарийн төвөгтэй байдал юм O (N).

Сансрын нарийн төвөгтэй байдал

Массив дахь элементүүдийн давтамжийг хадгалах хэш хүснэгтийг хадгалж байгаа тул орон зайн нарийн төвөгтэй байдал O (N).

Ашигласан материал