배열 Leetcode 솔루션에서 사라진 모든 숫자 찾기-TutorialCup

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

차례

문제 정책

이 문제에서 우리는 정렬 정수 여기에는 1에서 N까지의 요소가 포함됩니다. 여기서 N은 배열의 크기입니다. 그러나 사라진 요소가 있고 그 자리에 일부 중복 요소가 있습니다. 우리의 목표는 사라진 모든 정수의 배열을 반환하는 것입니다.

예

Array = {1 , 2 , 5 , 6 , 2 , 5}

3 4

핀

Array = {1 , 2 , 3 , 4}

핀

접근 방식 (HashSet 사용)

배열의 모든 요소를 표시 한 다음 [1, N] 범위에서 반복하여 어떤 요소가 배열에서 사라 졌거나 누락되었는지 확인할 수 있습니다. 정수가 표시되었는지 여부를 저장하기 위해 해시 세트를 사용합니다.

암호알고리즘

해시 세트 초기화 mark [정수] 존재하는 요소를 저장합니다.
모든 요소에 대해 i 배열에서 :
- 추가 i 에 표
목록 / 벡터 초기화 결과 누락 된 요소를 배열에 저장
모든 요소에 대해 i 범위 : [1, N] :
- If i 에 존재하지 않습니다 표:
  - 추가 결과
반품 결과
결과 인쇄

배열 Leetcode 솔루션에서 사라진 모든 숫자 찾기 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    unordered_set <int> mark;
    for(int &i : a)
        mark.insert(i);
    int N = a.size();
    vector <int> result;
    for(int i = 1 ; i <= N ; i++)
        if(mark.find(i) == mark.end())
            result.emplace_back(i);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

자바 프로그램

import java.util.*;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashSet <Integer> mark = new HashSet <Integer>();
        for(int i : a)
            mark.add(i);

        for(int i = 1 ; i <= a.length ; i++)
            if(!mark.contains(i))
                result.add(i);

        return result;
    }
}

3 4

배열 Leetcode 솔루션에서 사라진 모든 숫자 찾기의 복잡성 분석

시간 복잡성

의 위에) 정수를 표시하기 위해 전체 배열을 한 번 탐색합니다. N = 배열의 크기.

공간 복잡성

의 위에) 배열에있는 모든 숫자를 해시 테이블에 저장하기 때문입니다. 공간 복잡성 기여도에서 출력 배열을 고려하지 않습니다.

접근 (In-place 수정)

이 문제에서 주목해야 할 점은 "배열은 항상 크기보다 작거나 같은 요소를 포함합니다"입니다. 즉, 고유 한 요소만큼 많은 인덱스가 있습니다. 또한 누락 된 요소는 항상 N (배열 크기)보다 작습니다. 이 제약을 사용하면 배열 자체를 사용하여 어떤 방식 으로든 정수의 존재를 저장할 수 있습니다. 예를 들어 다음과 같이 작성할 수 있다고 가정합니다. 참 / 거짓 요소의 인덱스에서 각각 존재 / 부재를 나타냅니다. 우리의 경우 배열에는 이미 요소가 포함되어 있으므로 이러한 종류의 저장 / 기억이 실현 가능하지 않은 것 같습니다. 그러나 모든 요소가 양수라는 것을 알고 있으므로 배열에서 요소를 보았는지 여부를 나타내는 표시로 "음수"를 사용할 수 있습니다. 다음을 사용하여 일부 인덱스에 저장된 실제 값을 가져올 수 있습니다. 순수한() 정수의 절대 값을 반환하는 함수. 이러한 방식으로 배열을 해시 맵과 컨테이너로 모두 사용할 수 있습니다.

예를 들어, 배열에서 '2'요소를 본 경우 Array [1] = -1 * Array [1]을 할당하여 요소 2가 배열에 표시되었음을 알 수 있습니다.

이 트릭은 인덱스에서 요소를 본 경우 저장할 배열을 제자리에서 조작합니다. i. 완료되면 [1, N] 범위에서 루프를 실행하여 음수가 아닌 모든 정수 (보이지 않았 음을 의미 함)를 찾아 필요한 결과를 인쇄 할 수 있습니다. 이것은 우리가 수 배열을 변경합니다.