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


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี อเมซอน เดอชอว์ อีเบย์ Google ไมโครซอฟท์
แถว HashMap การเรียงลำดับ

ในปัญหานี้เราได้รับสอง อาร์เรย์ ของจำนวนเต็มบวก องค์ประกอบทั้งหมดของอาร์เรย์ที่สองมีความแตกต่างกันและมีอยู่ในอาร์เรย์แรก อย่างไรก็ตามอาร์เรย์แรกสามารถมีองค์ประกอบที่ซ้ำกันหรือองค์ประกอบที่ไม่ได้อยู่ในอาร์เรย์ที่สอง

เราจำเป็นต้องเรียงลำดับอาร์เรย์แรกและส่งคืนโดยรักษาลำดับสัมพัทธ์ขององค์ประกอบให้เหมือนกับในอาร์เรย์ที่สอง องค์ประกอบที่ไม่มีอยู่ในอาร์เรย์ที่สองควรปรากฏที่ส่วนท้ายของอาร์เรย์ในลักษณะที่ไม่ลดลง องค์ประกอบในอาร์เรย์จะต้องมีค่าไม่เกิน 1000

ตัวอย่าง

Array1 = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99}
Array2 = {5 , 6 , 12}
5 5 6 6 12 1 4 4 7 99

คำอธิบาย: ลำดับขององค์ประกอบในอาร์เรย์ที่สองคือ 5,6 และ 12 ดังนั้นจึงปรากฏเป็นอันดับแรกในอาร์เรย์ผลลัพธ์ องค์ประกอบอื่น ๆ ได้แก่ 1, 4, 4, 7 และ 99 ซึ่งเรียงตามลำดับที่ไม่ลดลง

Array1 = {5 , 4 , 3 , 2 , 1}
Array2 = {1 , 2 , 3 , 4 , 5}
1 2 3 4 5

คำอธิบาย: เราจัดเรียงอาร์เรย์แรกอีกครั้งเพื่อให้องค์ประกอบของมันอยู่ในลำดับที่ใกล้เคียงกับอาร์เรย์ที่สอง

วิธีการ (เครื่องมือเปรียบเทียบที่กำหนดเอง)

เมื่อเราใช้วิธีการเรียงลำดับใด ๆ เราจะใช้การเปรียบเทียบระหว่างค่าสองค่าของอาร์เรย์เพื่อตัดสินใจลำดับสัมพัทธ์ ตัวอย่างเช่นในการจัดเรียงฟองเรามักจะเปรียบเทียบองค์ประกอบสององค์ประกอบที่อยู่ติดกันเพื่อให้องค์ประกอบที่เล็กกว่านั้นสามารถนำไปข้างหน้าในอาร์เรย์ได้ คำจำกัดความของคำว่า "เล็กกว่า" มาจากขนาดหรือมูลค่าขององค์ประกอบ โดยทั่วไปตัวดำเนินการ '<' จะตรวจสอบว่าค่า LHS หรือไม่ น้อยกว่า ค่า RHS ภาษาการเขียนโปรแกรมช่วยให้เราสามารถแก้ไขตัวดำเนินการเหล่านี้ให้ ล้นมือ ในรูปแบบที่พึงปรารถนา นี่คือสิ่งที่เราจะใช้ที่นี่ เทคนิคการเขียนโปรแกรมดังกล่าวที่เราใช้วิธีการเปรียบเทียบที่แตกต่างกันในการตัดสินใจสั่งซื้อเรียกว่าการเปรียบเทียบแบบกำหนดเองและเราทำได้โดยใช้ตัวเปรียบเทียบแบบกำหนดเอง

เราส่งผ่านอาร์กิวเมนต์อื่นในฟังก์ชันการจัดเรียงที่ช่วยให้เราสามารถเปรียบเทียบองค์ประกอบในรูปแบบที่เราต้องการได้ เพื่อให้เข้าใจการทำงานทั่วไปให้เราตรวจสอบรหัสต่อไปนี้:

vector <int> a = {1 , 2 , 3 , 7 , 4};
sort(a.begin() , a.end() , [&](const int &first , const int &second){
    return first > second;
});

ในข้อมูลโค้ดด้านบนตัวเปรียบเทียบจะตรวจสอบว่าเป็นค่าหรือไม่ เป็นครั้งแรก ควรมาก่อนมูลค่า ที่สอง ในอาร์เรย์จำนวนเต็ม ตัวเปรียบเทียบควรส่งคืน จริง ถ้าเราต้องการ เป็นครั้งแรก มาก่อน ที่สอง. ไม่งั้นเรากลับ เท็จ. โค้ดด้านบนเป็นภาพประกอบที่เราจัดเรียงอาร์เรย์ตามลำดับที่ลดลง ในทำนองเดียวกันใน Java เราใช้ไฟล์ เครื่องเปรียบเทียบ () คลาสเพื่อตัดสินใจลำดับของสองอาร์กิวเมนต์ที่ส่งผ่านไป ทำการเปรียบเทียบ 3 ทางโดยส่งกลับค่า -1, 0 และ 1 หาก เป็นครั้งแรก อาร์กิวเมนต์น้อยกว่า ที่สองมันจะกลับมา -1. หากอาร์กิวเมนต์แรกมากกว่าอาร์กิวเมนต์ที่สองจะส่งกลับ 1. 0, มิฉะนั้น.

ขั้นตอนวิธี

  1. เริ่มต้นแผนที่แฮช ตำแหน่ง <> เพื่อแฮชดัชนีขององค์ประกอบในอาร์เรย์ที่สองไปยังดัชนีตามลำดับ
  2. เรียงลำดับอาร์เรย์แรก แต่ด้วยการส่งผ่านฟังก์ชันตัวเปรียบเทียบ (โดยใช้ฟังก์ชันแลมบ์ดาใน C ++ หรืออินเตอร์เฟสตัวเปรียบเทียบ <> ใน Java)
  3. ตัวเปรียบเทียบทำงานกับสองค่า เป็นครั้งแรก และ ที่สอง ดังต่อไปนี้:
    1. If ตำแหน่ง [แรก] และ ตำแหน่ง [วินาที] ไม่อยู่:
      1. เราต้องการให้องค์ประกอบที่เล็กกว่ามาก่อนจึงกลับมา แรก <วินาที
    2. If ตำแหน่ง [แรก] ไม่มีอยู่:
      1. เรากลับ เท็จ as เป็นครั้งแรก ควรมาในภายหลังในอาร์เรย์
    3. If ตำแหน่ง [วินาที] ไม่มีอยู่:
      1. การส่งคืนสินค้า จริง
    4. การส่งคืนสินค้า ตำแหน่ง [แรก] <ตำแหน่ง [วินาที]
  4. พิมพ์ผลลัพธ์

การใช้งานโซลูชัน Leetcode เรียงลำดับญาติ

โปรแกรม C ++

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

vector<int> relativeSortArray(vector<int>& Array1 , vector<int>& Array2)
{
    unordered_map <int , int> position;

    for(int i = 0 ; i < Array2.size() ; i++)
        position[Array2[i]] = i;

    sort(Array1.begin() , Array1.end() , [&](const int &first , const int &second)
     {
         if(position.find(first) == position.end() && position.find(second) == position.end())
             return first < second;
         if(position.find(first) == position.end())
             return false;
         if(position.find(second) == position.end())
             return true;
         return position[first] < position[second];
     });

    return Array1;
}

int main()
{
    vector <int> a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99} , b = {5 , 6 , 12};
    a = relativeSortArray(a , b);
    for(int &element : a)
        cout << element << " ";
    return 0;
}

โปรแกรม Java

import java.util.*;

class relative_sort
{
    public static void main(String args[])
    {
        int[] a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99};
        int[] b = {5 , 6 , 12};
        a = relativeSortArray(a , b);
        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }

    static int[] relativeSortArray(int[] Array1, int[] Array2) {
        Hashtable <Integer , Integer> position = new Hashtable<>();
        for(int i = 0 ; i < Array2.length ; i++)
            position.put(Array2[i] , i);

        Integer[] _Array1 = new Integer[Array1.length];
        for(int i = 0 ; i < _Array1.length ; i++)
            _Array1[i] = Array1[i];

        Arrays.sort(_Array1 , new Comparator<Integer>()
                    {
                        public int compare(Integer first , Integer second)
                        {
                            if(position.get(first) == null && position.get(second) == null)
                                return first - second;
                            if(position.get(first) == null)
                                return 1;
                            if(position.get(second) == null)
                                return -1;
                            return position.get(first) - position.get(second);
                        }
                    });

        for(int i = 0 ; i < Array1.length ; i++)
            Array1[i] = _Array1[i];
        return Array1;
    }
}
5 5 6 6 12 1 4 4 7 99

การวิเคราะห์ความซับซ้อนของโซลูชัน Leetcode เรียงลำดับญาติ

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

O (สูงสุด (NlogN, M)) ที่ไหน N = ขนาดของอาร์เรย์แรกและ M = ขนาดของอาร์เรย์ที่สอง เรารันการส่งผ่านเพียงครั้งเดียวในอาร์เรย์ที่สองซึ่งใช้เวลา O (M) และเรียงลำดับอาร์เรย์แรกซึ่งใช้เวลา O (NlogN) โดยสมมติว่าการเปรียบเทียบดำเนินการในเวลาคงที่

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

O (ม) ในขณะที่เราจัดเก็บดัชนีขององค์ประกอบของอาร์เรย์ที่สองในแผนที่แฮช

วิธีการ (การนับเรียงลำดับ)

ให้สมมติ Array1 = {1, 2, 2, 2} และ Array2 = {2, 1} เริ่มสำรวจอาร์เรย์ที่สอง เราเห็นจำนวนเต็ม 2 ก่อน ถ้าเรารู้ว่ามี 3 2 เราจะเขียนค่าเหล่านี้ได้อย่างง่ายดายใน Array1 โดยเริ่มจากดัชนี 0 จากนั้นเรามีจำนวนเต็ม 1 ใน Array2 อีกครั้งถ้าเรารู้ความถี่ของมันเราจะเก็บไว้ได้อย่างง่ายดายหลังจากสองครั้ง ในทำนองเดียวกันเราสามารถจัดเก็บความถี่ขององค์ประกอบทั้งหมดใน Array1 จากนั้นเรียกใช้ Array2 เพียงครั้งเดียวเขียนองค์ประกอบใน Array1 ใหม่ตามความถี่

แต่ถึงแม้หลังจากนั้นเราจะเพิกเฉยต่อองค์ประกอบเหล่านั้นซึ่งมีอยู่ใน Array1 แต่ไม่ใช่ใน Array2 ดังนั้นเราจึงเรียกใช้การวนซ้ำจากขีด จำกัด ล่างไปจนถึงการตรวจสอบขีด จำกัด บนสำหรับทุกองค์ประกอบที่มีความถี่เหลืออยู่และเขียนลงใน Array1 เนื่องจากเราเพิ่มขึ้นจากขีด จำกัด ล่างขึ้นไปบนเราจะจัดเรียงองค์ประกอบ "พิเศษ" เหล่านี้ในลักษณะที่ไม่ลดลง

ขั้นตอนวิธี

  1. เริ่มต้นอาร์เรย์: ความถี่ ขนาด 1000 เพื่อจัดเก็บความถี่ขององค์ประกอบใน Array1 และ idx เพื่อทราบตำแหน่งที่จะเขียนองค์ประกอบใน Array1 อีกครั้ง
  2. สำหรับทุกองค์ประกอบ ใน Array2:
    • ในขณะที่ ความถี่ [i]> 0:
      • กำหนด Array1 [idx] = i
      • idx ++
      • ความถี่ [i] -
  3. สำหรับทุกองค์ประกอบ i ในช่วง: [0, 4000]:
    • ในขณะที่ ความถี่ [i]> 0:
      • กำหนด Array1 [idx] = i
      • idx ++
      • ความถี่ [i] -
  4. พิมพ์ผลลัพธ์

การใช้งานโซลูชัน Leetcode เรียงลำดับญาติ

โปรแกรม C ++

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

vector <int> relativeSortArray(vector <int> &Array1 , vector <int> &Array2)
{
    vector <int> frequency(1010 , 0);
    for(int &x : Array1)
        frequency[x]++;

    int idx = 0;

    for(int &i : Array2)
    {
        while(frequency[i] > 0)
            Array1[idx++] = i , frequency[i]--;
    }

    for(int i = 0 ; i < 1010 ; i++)
        while(frequency[i] > 0)
            Array1[idx++] = i , frequency[i]--;

    return Array1;
}

int main()
{
    vector <int> a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99} , b = {5 , 6 , 12};
    a = relativeSortArray(a , b);
    for(int &element : a)
        cout << element << " ";
    return 0;
}

โปรแกรม Java

import java.util.*;

class relative_sort
{
    public static void main(String args[])
    {
        int[] a = {4 , 5 , 6 , 4 , 5 , 6 , 7 , 1 , 12 , 99};
        int[] b = {5 , 6 , 12};
        a = relativeSortArray(a , b);
        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }

    static int[] relativeSortArray(int[] Array1 , int[] Array2)
    {
        int[] frequency = new int[1010];
        for(int i = 0 ; i < 1010 ; i++)
            frequency[i] = 0;

        for(int i = 0 ; i < Array1.length ; i++)
            frequency[Array1[i]]++;

        int idx = 0;

        for(int i = 0 ; i < Array2.length ; i++)
        {
            while(frequency[Array2[i]] > 0)
            {
                Array1[idx++] = Array2[i];
                frequency[Array2[i]]--;
            }
        }

        for(int i = 0 ; i < 1010 ; i++)
            while(frequency[i] > 0)
            {
                Array1[idx++] = i;
                frequency[i]--;
            }

        return Array1;
    }
}
5 5 6 6 12 1 4 4 7 99

การวิเคราะห์ความซับซ้อนของโซลูชัน Leetcode เรียงลำดับญาติ

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

O (สูงสุด (N, M, 1000)) ในขณะที่เราเก็บความถี่ขององค์ประกอบของอาร์เรย์แรกในแผนที่แฮชโดยใช้เวลา O (N) จากนั้นสำหรับทุกองค์ประกอบในอาร์เรย์ที่สองเราจะเขียนมันในอาร์เรย์แรกต่อไปจนกว่าความถี่ของมันจะกลายเป็น 0 ในที่สุดเราจะตรวจสอบทุกองค์ประกอบในช่วง [0, 4000] เพื่อเติมเต็มในองค์ประกอบด้านซ้าย

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

O (1) เมื่อเราใช้พื้นที่คงที่ซึ่งเท่ากับ O (1000) ในกรณีนี้เพื่อเก็บความถี่ขององค์ประกอบ