ผสานโซลูชัน Leetcode อาร์เรย์ที่เรียงลำดับ


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี อเมซอน แอปเปิล บลูมเบิร์ก ByteDance ซิสโก้ อีเบย์ Expedia Facebook แซคส์โกลด์แมน Google ไอบีเอ็ม LinkedIn lyft ไมโครซอฟท์ Netflix คำพยากรณ์ ฉาก Uber VMware yahoo 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. พิมพ์ผลลัพธ์ที่ต้องการ

การใช้งาน Merge Sorted Arrays Leetcode Solution

โปรแกรม 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

การวิเคราะห์ความซับซ้อนของ Merge Sorted Arrays Leetcode Solution

ความซับซ้อนของเวลา

โอ (KlogK)ที่นี่มี K = N + ม. N = ขนาดของอาร์เรย์แรก M = ขนาดของอาร์เรย์ที่สอง ในขณะที่เราจัดเรียงอาร์เรย์แรกหลังจากเก็บองค์ประกอบ N + M ทั้งหมดแล้ว

ความซับซ้อนของอวกาศ

O (1) เนื่องจากหน่วยความจำคงที่ใช้สำหรับตัวแปร

แนวทาง (สองตัวชี้)

เราสามารถใช้ สองตัวชี้ เทคนิคในการรวมอาร์เรย์ที่เรียงลำดับสองอาร์เรย์เข้าด้วยกันเป็นอาร์เรย์ใหม่ แต่การสร้างอาร์เรย์ใหม่นี้จะต้องใช้พื้นที่เพิ่ม เราสามารถพยายามหลีกเลี่ยงอาร์เรย์พิเศษนี้โดยเฉพาะอย่างยิ่งเมื่ออาร์เรย์แรกมีพื้นที่เพียงพอที่จะเก็บองค์ประกอบทั้งหมดของอาร์เรย์ทั้งสอง เราสามารถใช้พอยน์เตอร์สองตัวและเริ่มรวมองค์ประกอบที่ด้านหลังของอาร์เรย์แรก

วิธีนี้จะช่วยตัดปัญหาของ "หน่วยความจำอาร์เรย์เพิ่มเติม" ในขณะที่เราแก้ไของค์ประกอบในช่องว่าง

ผสานโซลูชัน Leetcode อาร์เรย์ที่เรียงลำดับ

ขั้นตอนวิธี

  1. เริ่มต้นสองตัวแปร i และ j การจัดเก็บดัชนีขององค์ประกอบสุดท้ายของอาร์เรย์ที่หนึ่งและที่สองตามลำดับ
    • ผม = M - 1, j = N - 1
  2. เริ่มต้นตัวแปร idxจัดเก็บดัชนีสุดท้ายของอาร์เรย์แรกนั่นคือ:
    • idx = N + M - 1
  3. ตอนนี้ทำสิ่งต่อไปนี้จนถึงข้อใดข้อหนึ่ง i or j กลายเป็นศูนย์
    • ถ้า [i]> = b [j]
      • กำหนด [idx] = a [i], การลดลง i
    • อื่น
      • กำหนด [idx] = b [j], การลดลง j
    • การลดลง idx
  4. อย่างใดอย่างหนึ่ง ฉันหรือญ ไม่ใช่ศูนย์ซึ่งหมายความว่าองค์ประกอบบางส่วนยังไม่ได้รวมเข้าด้วยกัน เนื่องจากพวกเขาจะอยู่ในลักษณะที่เรียงกันอยู่แล้วเราจึงต่อท้ายอาร์เรย์แรกที่อยู่ด้านหน้า
  5. ในขณะที่ i ไม่กลายเป็นศูนย์
    1. กำหนด [idx] = a [i]
    2. การลดลง idx และ i
  6. ในขณะที่ j ไม่กลายเป็นศูนย์
    1. กำหนด [idx] = b [j]
    2. การลดลง idx และ j
  7. ตอนนี้อาร์เรย์แรกมีองค์ประกอบทั้งหมดตามลำดับการจัดเรียงที่ต้องการ

การใช้งาน Merge Sorted Arrays Leetcode Solution

โปรแกรม 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

การวิเคราะห์ความซับซ้อนของ Merge Sorted Arrays Leetcode Solution

ความซับซ้อนของเวลา

O (N + M). N = ขนาดของอาร์เรย์แรก M = ขนาดของอาร์เรย์ที่สอง ในขณะที่เราสำรวจทั้งสองอาร์เรย์หนึ่งครั้ง

ความซับซ้อนของอวกาศ

O (1), ในขณะที่เราเก็บองค์ประกอบทั้งหมดไว้ในอาร์เรย์แรก ดังนั้นอัลกอริทึมคือ ในสถานที่.