시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
정수가 주어집니다 정렬 A, k 번째 고유 요소를 배열로 인쇄합니다. 주어진 배열은 중복을 포함 할 수 있으며 출력은 배열의 모든 고유 요소 중에서 k 번째 고유 요소를 인쇄해야합니다. k가 고유 요소의 개수보다 많으면보고하십시오.
차례
예
입력:
A [] = {3,4,4,1,2,3}
K = 2
출력:
K 번째 비 반복 요소는 2입니다.
설명 :
첫 번째 비 반복 요소는 1이고
두 번째 비 반복 요소는 2입니다.
접근 방식 1 : 무차별 대입
주요 아이디어
발견 한 반복되지 않는 요소의 수를 저장할 개수 변수를 유지합니다. 이제 모든 요소를 반복하고 각 요소에 대해 이것이 반복되지 않는 요소인지 아닌지 확인하기 위해 배열을 반복 할 것입니다. 그렇다면 카운트를 1 씩 증가시킬 것입니다. K와 같으면 해당 요소를 인쇄합니다.
배열에서 K 번째 고유 요소에 대한 알고리즘
- 배열의 고유 요소 수를 계산하는 XNUMX으로 변수 수를 초기화합니다.
- 0에서 n-1 사이의 I에 대해 루프 실행
- A [i]가 반복 요소 인 경우 true이고 그 반대 인 경우 false로 플래그를 선언합니다.
- 0 ~ n-1 범위에서 j에 대해 루프 실행
- I가 j가 아니고 A [i]가 A [j]와 같으면 flag = true를 할당하고 중단합니다.
- 플래그가 거짓이면 1 씩 증가합니다.
- 카운트가 K와 같으면 A [i]를 인쇄합니다.
- 반품
실시
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 번째 고유 요소에 대한 알고리즘
- 배열의 각 요소의 빈도를 저장할 해시 테이블을 선언하십시오.
- 배열의 고유 요소 수를 계산하는 XNUMX으로 변수 수를 초기화합니다.
- 0에서 n-1 사이의 I에 대해 루프 실행
- A [i]의 주파수가 1이면 1 씩 증가합니다.
- 개수가 K와 같으면 A [i]를 인쇄합니다.
- 반품
예 :
A [] = {3,4,4,1,2,3}
K = 2
해시 테이블은 다음과 같습니다.
실시
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 번째 고유 요소에 대한 복잡도 분석
시간 복잡성
배열을 두 번만 반복합니다. 따라서 총 시간 복잡성은 의 위에).
공간 복잡성
배열에있는 요소의 빈도를 저장하기 위해 해시 테이블을 유지하고 있습니다. 따라서 공간 복잡성은 의 위에).
