정확히 K 회 반복되는 최소 요소


난이도 중급
자주 묻는 질문 Belzabar Komli Media 네트 스코프 엔비디아 운영 ServiceNow UHG 옵텀
배열 해시

크기 n에 배열 A []가 주어집니다. 우리는 정확히 k 번 반복되는 가장 작은 요소를 찾아야합니다. 정렬.

입력

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

K = 3

산출

주파수 K의 최소 요소 : 2

접근 방식 1 : 무차별 대입

주요 아이디어

배열의 모든 요소에 대해 전체 배열을 순회하여 빈도를 찾을 수 있으며 빈도가 K와 같으면 이전 답변과이 요소의 최소값을 취합니다. 마지막으로 최종 답변을 인쇄합니다.

정확히 K 번 반복되는 가장 작은 요소를 찾기위한 알고리즘

  1. false로 변수 'flag'를 초기화하십시오. 플래그는 주파수가 K 인 요소를 찾았는지 여부를 나타냅니다.
  2. 0에서 n-1 사이의 I에 대해 루프 실행
    1. 배열에서 A [i]의 주파수를 계산할 변수 개수를 XNUMX으로 초기화합니다.
    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 번 반복되는 가장 작은 요소를 찾기위한 알고리즘

  1. 각 요소가 해시 테이블에있는 경우 빈도를 저장하십시오.
  2. false로 변수 'flag'를 초기화하십시오. 플래그는 주파수가 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 회 반복되는 가장 작은 원소를 찾기위한 복잡성 분석

시간 복잡성

어레이를 한 번만 순회하므로 시간 복잡성은 의 위에).

공간 복잡성

배열에 요소의 빈도를 저장하기 위해 해시 테이블을 유지하므로 공간 복잡성이 의 위에).

참조