Релативно решение за низа лек-кодови


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон ДЕ Шо eBay 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;
});

Во горенаведената парче код, компараторот проверува дали има вредност прва треба да дојде пред вредност вториот во цела низа. Компараторот треба да се врати вистина ако сакаме прва да дојде претходно вториот. Инаку, се враќаме лажни. Горенаведениот код е илустрација каде ја сортираме низата во редослед на опаѓање. Слично на тоа, во Јава, ние користиме a Компаратор () класа да одлучи за редоследот на два аргументи пренесени на неа. Врши 3-насочна споредба со враќање на -1, 0 и 1. Ако е тоа прва аргументот е помал од вториот, се враќа -1. Друго, ако првиот аргумент е поголем од вториот, тој се враќа 1. 0, инаку

Алгоритам

  1. Иницијализирајте хаш-мапа позиција <>> да се хашираат индексите на елементи во втората низа на нивните соодветни индекси
  2. Сортирајте ја првата низа, но со поминување на функцијата за споредување (користете ја функцијата ламбда во C ++ или компараторот <> интерфејс во Јава)
  3. Компараторот работи на две вредности прва вториот како што следува:
    1. If позиција [прва] позиција [втора] не постојат:
      1. Ние сакаме помалиот елемент да дојде на прво место, затоа вратете се прво <второ
    2. If позиција [прва] не постои:
      1. Се враќаме лажни as прва треба да дојде подоцна во низата
    3. If позиција [втора] не постои:
      1. Врати се вистина
    4. Врати се позиција [прва] <позиција [втора]
  4. Печатете го резултатот

Имплементација на релативно сортирање на решенија за низа кодови

Програма 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

Анализа на комплексноста на решението за лет-код на релативната поделба на низата

Временска комплексност

О (максимум (NlogN, М)) каде N = големина на првата низа и M = големина на втората низа. Ние извршуваме единечен премин на втората низа што трае O (M) и го подредуваме првиот ред кој трае O (NlogN) време под претпоставка дека споредбата е извршена во константно време.

Комплексноста на просторот

О (М) како што ги зачувуваме индексите на елементи од втората низа во хаш-мапа.

Пристап (сметање на сортирање)

Да претпоставиме Array1 = {1, 2, 2, 2} и Array2 = {2, 1}. Започнете да ја разминувате втората низа. Прво гледаме цел број 2. Ако знаевме дека има 3 2, лесно ќе ги запишевме овие вредности во Array1 почнувајќи од индексот 0. Потоа, имаме цел број 1 во Array2. Повторно, ако ја знаевме нејзината фреквенција, лесно ќе ги чувавме по двајца. На сличен начин, можеме да ги зачуваме фреквенциите на сите елементи во Array1 и потоа да извршиме еден премин на Array2, повторно да ги запишеме елементите во Array1 според нивните фреквенции.

Но, дури и после тоа, ние би ги игнорирале оние елементи што се присутни во Array1, но не и во Array2. Значи, ние извршуваме јамка од долната граница до горната граница за проверка за секој елемент што има одредена фреквенција и ја запишуваме во Array1. Бидејќи се искачуваме од долната граница до горната, ќе ги сортираме овие „дополнителни“ елементи на не-опаѓачки начин.

Алгоритам

  1. Иницијализирај низа: фреквенција со големина 1000 за зачувување на фреквенциите на елементите во низата1 и idx да ја знаете позицијата повторно да напишете елементи во Array1.
  2. За секој елемент во низа2:
    • Додека фреквенција [i]> 0:
      • Доделување низа1 [idx] = т.е.
      • idx ++
      • фреквенција [i] -
  3. За секој елемент i во опсег: [0, 4000]:
    • Додека фреквенција [i]> 0:
      • Доделување низа1 [idx] = т.е.
      • idx ++
      • фреквенција [i] -
  4. Печатете го резултатот

Имплементација на релативно сортирање на решенија за низа кодови

Програма 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

Анализа на комплексноста на решението за лет-код на релативната поделба на низата

Временска комплексност

О (максимум (Н, М, 1000)) како што ја зачувуваме фреквенцијата на елементите од првата низа во хаш-мапа земајќи O (N) време. Потоа, за секој елемент во втората низа, продолжуваме да ги пишуваме во првата низа додека нивните фреквенции не станат 0. Конечно, проверуваме дали има секој елемент во опсегот [0, 4000] за да се пополни кој било лев елемент.

Комплексноста на просторот

О (1) бидејќи ние користиме постојан простор што е еднаков на О (1000) во овој случај за да ја зачуваме фреквенцијата на елементите.