合併排序數組Leetcode解決方案  


難度級別 容易獎學金
經常問 土磚 亞馬遜 蘋果 彭博社 ByteDance 思科 易趣 Expedia的 Facebook 高盛 谷歌 IBM LinkedIn lyft Microsoft微軟 Netflix公司 神諭 畫面 尤伯杯 VMware的 雅虎 Yandex的
算法 排列 編碼 訪問 面試準備 力碼 力碼解決方案 兩指針

在“合併排序數組”問題中,我們得到兩個 數組 以降序排列。 第一個數組未完全填充,並且具有足夠的空間來容納第二個數組的所有元素。 我們必須合併兩個數組,以便第一個數組包含兩個數組的元素並在其中排序 不降序 秩序。

例  

{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. 打印所需的結果

合併排序數組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;
}

Java程序

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元素之後對第一個數組進行排序時。

也可以看看
增加減少的字符串Leetcode解決方案

空間複雜度

O(1) 因為常量存儲器用於變量。

方法(兩個指針)  

我們可以使用 兩分球 將兩個排序後的數組合併為一個新數組的技術。 但是,創建此新陣列將花費額外的空間。 我們可以嘗試避免這種額外的數組,特別是當第一個數組具有足夠的空間來容納兩個數組的所有元素時。 我們可以使用兩個指針並開始合併第一個數組後面的元素。

當我們將元素固定在空白空間中時,這將消除“額外的數組內存”的問題。

合併排序數組Leetcode解決方案

算法

  1. 初始化兩個變量 ij 分別存儲第一數組和第二數組的最後一個元素的索引。
    • i = M – 1,j = N – 1
  2. 初始化變量 IDX,存儲第一個數組的最後一個索引,即:
    • idx = N + M – 1
  3. 現在,執行以下操作,直到 i or j 變為零
    • 如果a [i]> = b [j]
      • 分配a [idx] = a [i],遞減 i
    • 其他
      • 分配a [idx] = b [j],遞減 j
    • 減量 IDX
  4. 兩者之一 我或j 不為零,表示某些元素尚未合併。 由於它們已經採用了排序方式,因此我們只需將它們附加到前面的第一個數組中即可。
  5. i 不為零
    1. 分配a [idx] = a [i]
    2. 減量 IDXi
  6. j 不為零
    1. 分配a [idx] = b [j]
    2. 減量 IDXj
  7. 現在,第一個數組具有按所需排序順序的所有元素。

合併排序數組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;
}

Java程序

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 =第二個數組的大小。 當我們遍歷兩個數組一次時。

也可以看看
四個Leetcode解決方案的力量

空間複雜度

O(1), 因為我們將所有元素存儲在第一個數組中。 所以,算法是 到位.