정렬 된 배열 병합 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance 시스코 이베이 Expedia Facebook 골드만 삭스 구글 IBM 링크드인 리프트 Microsoft 넷플릭스 신탁 Tableau 동네 짱 VM웨어 Yahoo Yandex 주차
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 두 포인터조회수 115

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

“Merge Sorted Arrays”문제에서 우리는 배열 내림차순이 아닌 순서로 정렬됩니다. 첫 번째 배열은 완전히 채워지지 않았으며 두 번째 배열의 모든 요소를 ​​수용 할 수있는 충분한 공간이 있습니다. 첫 번째 배열이 두 배열의 요소를 포함하고 정렬되도록 두 배열을 병합해야합니다. 비 내림차순 주문.

{1 , 2 , 3 , - , - , -}
{2 , 6 , 7}
1 2 2 3 6 7
{1 , 1 , 1 ,  - , -}
{2 , 4}
1 1 1 2 4

접근 (정렬)

두 번째 배열의 모든 요소를 ​​첫 번째 배열로 전송할 수 있습니다. 그런 다음 첫 번째 배열을 정렬하여 필요한 결과를 얻을 수 있습니다.

암호알고리즘

  1. i = 0 ~ i = N 인 경우 할당
    1. a [i + m] = b [i], a = 첫 번째 배열, b = 두 번째 배열
  2. 첫 번째 배열 정렬
  3. 필요한 결과 인쇄

Merge Sorted Arrays Leetcode 솔루션 구현

C ++ 프로그램

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

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    for(int i = 0 ; i < n ; i++)
        a[i + m] = b[i];

    sort(a.begin() , a.end());
    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

자바 프로그램

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        for(int i = 0 ; i < n ; i++)
            a[i + m] = b[i];
        Arrays.sort(a);
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

병합 정렬 배열의 복잡성 분석 Leetcode 솔루션

시간 복잡성

O (KlogK)어디로 K = N + M. N = 첫 번째 배열의 크기, M = 두 번째 배열의 크기. N + M 요소를 모두 저장 한 후 첫 번째 배열을 정렬합니다.

공간 복잡성

O (1) 상수 메모리가 변수에 사용되기 때문입니다.

접근 (두 포인터)

우리는 사용할 수 있습니다 두 포인터 두 개의 정렬 된 배열을 새 배열로 병합하는 기술입니다. 그러나이 새로운 어레이를 생성하려면 추가 공간이 필요합니다. 특히 첫 번째 배열에 두 배열의 모든 요소를 ​​담을 수있는 충분한 공간이있는 경우이 추가 배열을 피할 수 있습니다. 두 개의 포인터를 사용하고 첫 번째 배열의 뒷면에있는 요소 병합을 시작할 수 있습니다.

이것은 우리가 빈 공간에있는 요소들을 계속 수정함에 따라“추가 어레이 메모리”의 문제를 줄일 것입니다.

정렬 된 배열 병합 Leetcode 솔루션

암호알고리즘

  1. 두 변수 초기화 ij 첫 번째 배열과 두 번째 배열의 마지막 요소 인덱스를 각각 저장합니다.
    • 나는 = M – 1, j = N – 1
  2. 변수 초기화 idx, 첫 번째 배열의 마지막 인덱스를 저장합니다.
    • 아이디 = N + M – 1
  3. 이제 다음 중 하나가 될 때까지 다음을 수행하십시오. i or j XNUMX이된다
    • a [i]> = b [j]
      • 할당 a [idx] = a [i], 감소 i
    • 다른
      • 할당 a [idx] = b [j], 감소 j
    • 감소 idx
  4. 다음 중 하나 i 또는 j XNUMX이 아니므로 일부 요소가 아직 병합되지 않았습니다. 이미 정렬 된 방식이므로 앞의 첫 번째 배열에 추가하기 만하면됩니다.
  5. DaVinci에는 i XNUMX이되지 않고
    1. a [idx] = a [i] 할당
    2. 감소 idxi
  6. DaVinci에는 j XNUMX이되지 않고
    1. a [idx] = b [j] 할당
    2. 감소 idxj
  7. 이제 첫 번째 배열에는 필요한 정렬 순서로 모든 요소가 있습니다.

Merge Sorted Arrays Leetcode 솔루션 구현

C ++ 프로그램

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

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    int i = m - 1 , j = n - 1 , idx = m + n - 1;
    while(i >= 0 && j >= 0)
    {
        if(a[i] >= b[j])
        {
            a[idx] = a[i];
            i--;
        }
        else
        {
            a[idx] = b[j];
            j--;
        }
        idx--;
    }


    while(i >= 0)
        a[idx--] = a[i--];

    while(j >= 0)
        a[idx--] = b[j--];

    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

자바 프로그램

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        int i = m - 1 , j = n - 1 , idx = m + n - 1;
        while(i >= 0 && j >= 0)
        {
            if(a[i] >= b[j])
            {
                a[idx] = a[i];
                i--;
            }
            else
            {
                a[idx] = b[j];
                j--;
            }
            idx--;
        }

        while(i >= 0)
            a[idx--] = a[i--];

        while(j >= 0)
            a[idx--] = b[j--];

        return;
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

병합 정렬 배열의 복잡성 분석 Leetcode 솔루션

시간 복잡성

O (N + M). N = 첫 번째 배열의 크기, M = 두 번째 배열의 크기. 우리가 두 배열을 한 번 횡단하면서.

공간 복잡성

O (1), 모든 요소를 ​​첫 번째 배열에 저장하므로 그래서 알고리즘은 그 자리에서.

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