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

난이도 중급
자주 묻는 질문 벨자바르 콤리미디어 네트 스코프 엔비디아 운영 ServiceNow UHG 옵텀
배열 해시 조회수 116

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

크기 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 회 반복되는 가장 작은 원소를 찾기위한 복잡성 분석

시간 복잡성

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

공간 복잡성

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

참조

균열 시스템 설계 인터뷰
Translate »