Харьцуулах ангиллын массивын Leetcode шийдэл  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны DE Шоу Ebay Google-ийн Microsoft-
алгоритмууд Array кодлох HashMap ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions Ангилах

Энэ асуудалд бид хоёрыг өгдөг массивууд эерэг бүхэл тоонууд. Хоёрдахь массивын бүх элементүүд ялгаатай бөгөөд эхний массивт байдаг. Гэхдээ эхний массив нь давхардсан элементүүд эсвэл хоёр дахь массивт байхгүй элементүүдийг агуулж болно.

Бид эхний массивыг эрэмбэлж, элементүүдийн харьцангуй дарааллыг хоёр дахь массивтай адил байлгах хэрэгтэй. Хоёрдахь массивт байхгүй элементүүд массивын төгсгөлд буурахгүй байх ёстой. Массив дахь элементүүд 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 дээр бид a Харьцуулагч () түүнд дамжуулсан хоёр аргументийн дарааллыг шийдэх анги. Энэ нь -3, 1, 0-ийг буцааж 1 талын харьцуулалтыг гүйцэтгэдэг эхний аргумент нь -ээс бага байна хоёр дахь, буцаж ирдэг -1. Эхний аргумент нь хоёр дахь хэмжээнээс их байвал буцаана 1. , өөрөөр.

Алгоритм

  1. Хэш газрын зургийг эхлүүлэх байрлал <> хоёрдахь массив дахь элементүүдийн индексийг тус тусын индекст хэш хийх
  2. Эхний массивыг эрэмбэлэх, гэхдээ харьцуулагч функцийг дамжуулж (C ++ дээр lambda функц эсвэл 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) хугацаа шаардагдах эхний массивыг эрэмбэлнэ.

мөн үзнэ үү
Энэ нь шулуун шугамын Leetcode шийдэл мөн эсэхийг шалгана уу

Сансрын нарийн төвөгтэй байдал

O (M) Хоёрдахь массивын элементүүдийн индексийг хэш газрын зураг дээр хадгалах үед.

Хандалт (Эрэмбэлэх тоолох)  

Array1 = {1, 2, 2, 2} ба Array2 = {2, 1} гэж үзье. Хоёрдахь массивыг дайрч эхэл. Бид бүхэл тоог 2-ыг хамгийн түрүүнд харж байна. Хэрэв бид 3 2 байгааг мэдэж байсан бол эдгээр утгуудыг 1 индексээс эхлэн Array0 дээр хялбархан бичих байсан. Дараа нь бид Array1 дотор бүхэл тоо 2-тэй байна. Дахин хэлэхэд, хэрэв бид түүний давтамжийг мэддэг байсан бол хоёр хоёроос хойш амархан хадгалах байсан. Үүнтэй адилаар бид 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] муж дахь элемент бүрийг шалгана.

мөн үзнэ үү
Тоог багасгахын тулд хэдэн алхам хийхийг сонгосон Leetcode шийдэл

Сансрын нарийн төвөгтэй байдал

O (1) элементүүдийн давтамжийг хадгалахын тулд энэ тохиолдолд O (1000) -тай тэнцүү тогтмол зайг ашигладаг тул.