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

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 구글 Microsoft Yahoo
알고리즘 배열 코딩 해싱 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 43

문제 정책

이 문제에서 우리는 정렬 정수 여기에는 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) 일정한 메모리 공간을 사용하므로

코멘트를 남겨

Translate »
1