Массивті басқа массивпен анықталған тәртіп бойынша сұрыптаңыз  


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Microsoft SAP зертханалары Snapchat Yahoo Зохо
Array іздеу Сұрыптау

Проблемалық мәлімдеме  

Сізге екі беріледі массивтер of бүтін сандар arr1 [] және arr2 []. «Массивті басқа массивпен анықталған тәртіпке сәйкес сұрыптау» сұрағы сорт екінші жиымға сәйкес бірінші жиым, бірінші жиымдағы сандар жиымдағы барлық мәндерді салыстырмалы түрде сұрыптайтын болады []. Ал екінші жиымда жоқ бірінші жиымдағы элементтер сұрыпталған тәртіпте жиымның соңына енгізіледі.

мысал  

arr1[] = { 2,1,2,5,1,3,6,8,8 }

arr2[] = { 2,1,8,3}
2 2 1 1 8 8 3 5 6

Түсіндіру

A1 A2 бойынша сұрыпталады.

Массивті басқа массивпен анықталған тәртіп бойынша сұрыптаңыз

 

Массивті басқа массивпен анықталған тәртіп бойынша сұрыптау алгоритмі  

1. Sort the array using the qsort method or comparator interface.
2. Search the value in arr2[] and find its index value.
3. Check if
  1. Both of the returned value is -1 if true then return the difference between the returned value.
  2. If one of the first returned values is -1 if true then return the -1.
  3. If the second returned value is -1, then return 1.
4. Else return the value of the difference of the input value.
5. Print the sorted array.

Түсіндіру  

Біз екеуін бердік бүтін сан массивтер. Содан кейін бізден сұрайды сорт екінші жиымға сәйкес бірінші массив. Массивтердің бірінде сұрыпталуға тиісті барлық мәндер бар. Ал басқа массивте бізде бірінші массивті сұрыптауға тура келетін бірнеше мәндер бар. Бұл дегеніміз, егер бізде екінші массивте (1, 2, 3, 4) берілген сан болса. Біз бірінші массивтегі барлық 1-ді іздеуіміз керек және оларды алдымен сұрыпталған түрде бірінші жиымға қоюымыз керек. Сонда бізде екінші массивте 2 бар. Бірінші жиымдағы барлық 2-ді тауып, содан кейін оларды бірінші жиымға салыңыз және т.б.

Сондай-ақ, қараңыз
Сөзді тап

Қажетті нәтижені білу үшін біз ішкі әдісті қолданатын боламыз. C ++ тілінде біз qsort әдісі, qsort әдісі - тез іздеу алгоритмі ретінде қолданылатын алдын-ала анықталған әдіс. Бұл кез-келген тізімді сұрыптауға арналған ең жылдам алгоритмдердің бірі. Java-да біз екінші жиымға сәйкес массивті сұрыптау үшін Комаратор интерфейсін қолданамыз. Әдіс екі мәнді таңдайды. Салыстыру үшін, содан кейін біз осы мәнді екінші жиымнан іздейміз. Егер ол екінші жиымда болса, онда ол екі мәннің индексін қайтарады, ол жоқ, содан кейін біз -1 мәнін қайтарамыз.

Біз бірнеше шарт жасадық. Егер біз қайтарылған екі мәнді де оң деп тапсақ. Содан кейін біз қайтарылған мәндердің айырмашылығын қайтарамыз. Егер бірінші мән оң болса, онда -1 қайтарылады. Егер екінші мән ғана оң болса, онда 1 мәнін қайтарады, егер жағдайдың ешқайсысы қанағаттандырмаса, онда бірінші жиымнан алынған мәндердің айырымын қайтарады. Барлық салыстырулардан кейін массив сұрыпталады. Соңында сұрыпталған массивті басып шығарыңыз.

код  

Массивті басқа массивпен анықталған тәртіп бойынша сұрыптауға арналған C ++ коды

#include <stdio.h>
#include<iostream>

using namespace std;

int Arr2[4];

int size = 4;

int searchElement(int key)
{
    int i;
    for (i = 0; i < size; i++)
        if (Arr2[i] == key)
            return i;
    return -1;
}

int compareValuesFromArray(const void* a, const void* b)
{
    int eleIndex1 = searchElement(*(int*)a);
    int eleIndex2 = searchElement(*(int*)b);
    if (eleIndex1 != -1 && eleIndex2 != -1)
        return eleIndex1 - eleIndex2;
    else if (eleIndex1 != -1)
        return -1;
    else if (eleIndex2 != -1)
        return 1;
    else
        return (*(int*)a - *(int*)b);
}

void sortAccAnotherArray(int A1[], int size1)
{
    qsort(A1, size1, sizeof(int), compareValuesFromArray);
}

int main()
{
    int Arr1[] = {1,4,2,4,6,4,7,2,2,3 };
    int Arr2[]= {1,2,3,4};
    int n = sizeof(Arr1) / sizeof(Arr1[0]);

    sortAccAnotherArray(Arr1, n);

    for (int i = 0; i <n; i++)
        printf("%d ", Arr1[i]);
    return 0;
}
1 2 2 2 3 4 4 4 6 7

Массивті басқа массивпен анықталған ретке сәйкес сұрыптауға арналған Java коды

import java.util.*;
import java.util.Arrays;

class SortAnArray
{
    private static int Arr1[] = { 1,4,2,4,6,4,7,2,2,3};
    private static int Arr2[]= {1,2,3,4};

    private static int size = Arr2.length;

    public static int searchElement(int key)
    {
        int i;
        for (i = 0; i < size; i++)
            if (Arr2[i] == key)
                return i;
        return -1;
    }

    public static void sortAccAnotherArray(int A1[], int size1)
    {
        Integer[]sortedArr = Arrays.stream(A1).boxed().toArray(Integer[]::new);

        Arrays.sort(sortedArr, new Comparator<Integer>()
        {
            public int compare(Integer o1, Integer o2)
            {

                int a = o1.intValue();
                int b = o2.intValue();

                int eleIndex1 = searchElement(a);
                int eleIndex2 = searchElement(b);

                if (eleIndex1 != -1 && eleIndex2 != -1)
                    return eleIndex1 - eleIndex2;
                else if (eleIndex1 != -1)
                    return -1;
                else if (eleIndex2 != -1)
                    return 1;
                else
                    return (a - b);
            }
        });
        int[] finalArr = Arrays.stream(sortedArr).mapToInt(Integer::intValue).toArray();
        System.out.println(Arrays.toString(finalArr));
    }

    public static void main(String [] args)
    {

        int n = Arr1.length;

        sortAccAnotherArray(Arr1, n);
    }

}

[1, 2, 2, 2, 3, 4, 4, 4, 6, 7]

Күрделілікті талдау  

Уақыттың күрделілігі

O (mn Logm) қайда «M» arr1 & ұзындығы «N» arr2 ұзындығы. Біз qsort (сұрыптау алгоритмі) қолданғандықтан. Біз қол жеткіздік O (n log n) фактор. Мұнда іздеу сызықтық іздеу арқылы жүзеге асырылады. Мұны істеудің орнына біз HashMap-ті оңай пайдалана алдық, бұл уақыттың күрделілігін төмендететін еді.

Сондай-ақ, қараңыз
K жиі кездесетін элементтер

Ғарыштың күрделілігі

O (log n), қайда «M» және «N» бұл Arr1 және Arr2 ұзындығы. Біз жылдам сұрыптаудың көмегімен сұрыптауды жасадық, сондықтан кеңістіктің күрделілігі соған байланысты. Бірақ бағдарлама тұтастай алғанда қажет O (N + M).