배열의 K 번째 고유 요소

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple ByteDance 이베이 Expedia Facebook 구글 링크드인 Microsoft 신탁 세일즈 포스 스포티 파이 월마트 연구소
분열과 정복 더미조회수 96

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

정수가 주어집니다 정렬 A, k 번째 고유 요소를 배열로 인쇄합니다. 주어진 배열은 중복을 포함 할 수 있으며 출력은 배열의 모든 고유 요소 중에서 k 번째 고유 요소를 인쇄해야합니다. k가 고유 요소의 개수보다 많으면보고하십시오.

입력:

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

K = 2

출력:

K 번째 비 반복 요소는 2입니다.

설명 :

첫 번째 비 반복 요소는 1이고

두 번째 비 반복 요소는 2입니다.

접근 방식 1 : 무차별 대입

주요 아이디어

발견 한 반복되지 않는 요소의 수를 저장할 개수 변수를 유지합니다. 이제 모든 요소를 ​​반복하고 각 요소에 대해 이것이 반복되지 않는 요소인지 아닌지 확인하기 위해 배열을 반복 할 것입니다. 그렇다면 카운트를 1 씩 증가시킬 것입니다. K와 같으면 해당 요소를 인쇄합니다.

배열에서 K 번째 고유 요소에 대한 알고리즘

  1. 배열의 고유 요소 수를 계산하는 XNUMX으로 변수 수를 초기화합니다.
  2. 0에서 n-1 사이의 I에 대해 루프 실행
    1. A [i]가 반복 요소 인 경우 true이고 그 반대 인 경우 false로 플래그를 선언합니다.
    2. 0 ~ n-1 범위에서 j에 대해 루프 실행
      1. I가 j가 아니고 A [i]가 A [j]와 같으면 flag = true를 할당하고 중단합니다.
    3. 플래그가 거짓이면 1 씩 증가합니다.
    4. 카운트가 K와 같으면 A [i]를 인쇄합니다.
  3. 반품

실시

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

JAVA 프로그램

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 번째 고유 요소에 대한 복잡도 분석

시간 복잡성

크기가 N 인 두 개의 중첩 루프를 사용합니다. 따라서 총 시간 복잡도는 다음과 같습니다. O (N ^ 2).

공간 복잡성

추가 공간을 사용하지 않으므로 공간 복잡성은 O (1).

접근 방식 2 : 해싱 사용

주요 아이디어

해시 테이블에 배열의 각 요소의 빈도를 저장합니다. 이제 우리는 발견 한 반복되지 않는 요소의 수를 저장할 개수 변수를 유지합니다. 다음으로 모든 요소를 ​​반복하고 각 요소에 대해 빈도가 1보다 큰지 확인하고 1과 같으면 개수를 1 씩 증가시킵니다. K와 같으면 해당 요소를 인쇄합니다.

배열에서 K 번째 고유 요소에 대한 알고리즘

  1. 배열의 각 요소의 빈도를 저장할 해시 테이블을 선언하십시오.
  2. 배열의 고유 요소 수를 계산하는 XNUMX으로 변수 수를 초기화합니다.
  3. 0에서 n-1 사이의 I에 대해 루프 실행
    1. A [i]의 주파수가 1이면 1 씩 증가합니다.
    2. 개수가 K와 같으면 A [i]를 인쇄합니다.
  4. 반품

예 :

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

K = 2

해시 테이블은 다음과 같습니다.

배열의 K 번째 고유 요소

실시

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

JAVA 프로그램

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 번째 고유 요소에 대한 복잡도 분석

시간 복잡성

배열을 두 번만 반복합니다. 따라서 총 시간 복잡성은 의 위에).

공간 복잡성

배열에있는 요소의 빈도를 저장하기 위해 해시 테이블을 유지하고 있습니다. 따라서 공간 복잡성은 의 위에).

참조

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