중복 포함

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple
배열 해싱조회수 108

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

우리는 주어진 정렬 중복 요소를 포함하거나 포함하지 않을 수 있습니다. 따라서 중복이 포함되어 있는지 확인해야합니다.

중복 포함

[1, 3, 5, 1]
true
[“apple”, “mango”, “orange”, “mango”]
true
[22.0, 4.5, 3.98, 45.6, 13.54]
false

접근

배열에 중복이 있는지 여부를 확인하기 위해 여러 가지 방법으로 배열을 확인할 수 있습니다. 가장 일반적인 방법은“Brute Force 방법”입니다. 그러나 그것은 O (n2) 학습 목적으로 만 적합합니다. 그러나 우리는 더 적은 시간 복잡성으로 문제를 해결하기 위해“해시 세트 방법”또는“해시 테이블 방법”이 방법이“Brute Force 방법”보다 훨씬 더 효율적입니다. Hash Set 메서드는 O (n)의 시간 복잡도를 사용합니다.

해시 설정 방법

이 방법은 다른 방법보다 훨씬 간단하고 효율적입니다. 세트에 중복이 포함되어 있지 않다는 것을 알아야합니다. 즉, 중복 값을 추가하려고하면 오류가 발생합니다. 이 방법을 사용하면 배열 요소를 반복해서 해시 세트에 삽입하기 만하면됩니다. 그런 다음 세트의 크기를 배열과 비교하십시오. 설정과 같지 않으면 배열에 중복 항목이 포함됩니다.

암호알고리즘

  1. 먼저 배열을 인수로 취하는 함수를 만듭니다.
  2. 그 후 함수에서 배열의 모든 값을 포함하는 집합을 만듭니다.
  3. 세트는 중복을 허용하지 않습니다. 즉, 배열에 중복이 포함 된 경우 해당 크기가 세트의 크기와 다릅니다.
  4. 마지막으로 배열과 집합의 크기를 비교합니다. 크기에 차이가 있으면 배열에 중복이 포함되고 모든 요소가 구별됩니다.

설명

우리 프로그램에서 우리는 중복을 확인하기 위해 해시 세트를 사용합니다. 먼저, 우리는 확인할 함수를 만들 것입니다. 여기에서 해시 세트를 만들고 배열의 모든 값을 제공합니다. 그 후 세트가 중복을 제거하고 배열과 비교하여 크기가 다르면 세트의 크기에 영향을 미치지 않습니다.

배열에 중복이 있는지 확인하는 C ++ 코드

#include <iostream>
#include <unordered_set>
using namespace std;

bool contain_duplicate(int arr[], int n)
{
    unordered_set<int> myset;
    bool flag = 0;

    for (int i = 0; i < n; i++)
    {
        if (myset.find(arr[i]) == myset.end())
            myset.insert(arr[i]);

        else
        {
            flag = 1;
            break;
        }

    }
    return flag;
}
int main()
{
    int arr[] = {1, 5, 2, 4, 3, 7, 8, 9, 1};
    int n = sizeof(arr) / sizeof(int);

    cout<< boolalpha <<contain_duplicate(arr, n);
    return 0;
}
true

배열에 중복이 있는지 확인하는 Java 코드

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class contain_duplicate
{

    public static boolean solution(Integer [] array)
    {

        Set<Integer> myset = new HashSet<> (Arrays.asList(array));

        if(array.length!=myset.size())
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public static void main(String[] args)
    {
        Integer [] array = { 1, 2, 3, 6, 4, 9, 8, 1};
        System.out.println(solution(array));

    }
}
true

복잡성 분석

시간 복잡성

O (n) 여기서 "n"은 배열의 크기입니다.

공간 복잡성

O (n)은 해시 테이블이 사용하는 공간이 그 안의 요소 수와 선형이기 때문입니다.

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