첫 번째 비 반복 요소 TutorialCup 첫 번째 비 반복 요소

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

Twitter Facebook 링크드인 버퍼 레딧 텀블러

배열 A가 주어집니다. 배열에서 반복되지 않는 첫 번째 요소를 찾아야합니다.

예

입력:

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

출력:

첫 번째 비 반복 요소 : 3

1, 2는 반복되기 때문에 답이 아니고 4는 답이 아니기 때문에 3가 아니라 4 인 첫 번째 non_repeating 요소를 찾아야하기 때문입니다.

접근 방식 1 : 무차별 대입

주요 아이디어

의 모든 요소에 대해 정렬, 전체 배열을 반복하고이 요소가 반복되지 않으면이 요소를 인쇄합니다.

암호알고리즘

0에서 n-1 사이의 I에 대해 루프 실행
1. 0에서 n 사이의 j에 대해 루프 실행
  1. j가 n과 같으면 A [i]를 인쇄하고 반환합니다.
  2. I가 j와 같지 않고 A [i]가 A [j]와 같으면이 루프에서 벗어나십시오.
2. 모든 요소가 배열에서 반복된다는 것을 인쇄하십시오.

첫 번째 비 반복 요소 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (j == n)
            {
                cout << "First non-repeating element is: " << A[i] << endl;
                return;
            }
            if (j != i and A[i] == A[j])
            {
                break;
            }
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}

First non-repeating element is: 3

JAVA 프로그램

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        int n = A.length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (j == n)
                {
                    System.out.println("First non-repeating element is: "+A[i]);
                    return;
                }
                if (j != i && A[i] == A[j])
                {
                    break;
                }
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}

First non-repeating element is: 3

첫 번째 비 반복 요소에 대한 복잡성 분석

시간 복잡성

크기가 N 인 두 개의 중첩 루프가 있으므로 총 시간 복잡도는 다음과 같습니다. O (N ^ 2).

공간 복잡성

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

접근 방식 2 : 해싱 사용

주요 아이디어

해시 테이블에 각 요소의 빈도를 저장할 수 있으며 그 후에 배열을 탐색하여 빈도가 1 인 첫 번째 요소를 찾을 수 있습니다.

암호알고리즘

각 요소의 빈도를 해시 테이블에 저장합니다.
0에서 n-1 사이의 I에 대해 루프 실행
1. 해시 테이블에서 A [i]의 빈도가 1이면 A [i]를 인쇄하고 반환합니다.
반복되는 배열의 모든 요소를 인쇄하십시오.

예를 들어 이해

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

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

핀