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


난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 구글 Microsoft Yahoo
배열 해싱

문제 정책

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

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

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

Array = {1 , 2 , 3 , 4}
n

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

접근 방식 (HashSet 사용)

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

암호알고리즘

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

배열 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] 범위에서 루프를 실행하여 음수가 아닌 모든 정수 (보이지 않았 음을 의미 함)를 찾아 필요한 결과를 인쇄 할 수 있습니다. 이것은 우리가 수 배열을 변경합니다.

암호알고리즘

  1. 모든 요소에 대해 배열에서 :
    • Array [i – 1]> 0 인 경우 :
      • 이를 음수로 설정하거나 Array [i – 1] * = -1;
  2. 목록 / 벡터 초기화 결과 모든 누락 된 요소를 저장하려면
  3. 모든 정수에 대해 범위 [1, N] (N = 배열 ​​크기) :
    • If 배열 [i]> 0
      • 이 요소 추가 i결과
  4. 반환 결과
  5. 결과 인쇄

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

C ++ 프로그램

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

vector <int> findDisappearedNumbers(vector <int> &a)
{
    int N = a.size();
    int idx;
    for(int i = 0 ; i < N ; i++)
    {
        idx = abs(a[i]) - 1;
        if(a[idx] > 0)
            a[idx] *= -1;
    }

    vector <int> result;
    for(int i = 0 ; i < N ; i++)
        if(a[i] > 0)
            result.emplace_back(i + 1);

    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.*;
import java.lang.Math;

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)
    {
        int idx;
        for(int i = 0 ; i < a.length ; i++)
        {
            idx = Math.abs(a[i]) - 1;
            if(a[idx] > 0)
                a[idx] *= -1;
        }

        List <Integer> result = new ArrayList <Integer> ();

        for(int i = 0 ; i < a.length ; i++)
            if(a[i] > 0)
                result.add(i + 1);

        return result;
    }
}
3 4

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

시간 복잡성

의 위에) 누락 된 요소를 찾기 위해 입력에 관계없이 배열을 두 번 실행합니다. N = 배열의 크기.

공간 복잡성 

O (1) 일정한 메모리 공간을 사용하므로