Տեսակավորել զանգվածը ըստ այլ զանգվածի կողմից սահմանված կարգի


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Microsoft SAP լաբորատորիաներ Snapchat Անտաշ անասուն նողկալի արարած Zoho
Դասավորություն Որոնում դասավորում

Խնդիրի հայտարարություն

Ձեզ երկուսն են տալիս զանգվածներ of ամբողջական թվերը arr1 [] և arr2 []: Հարց է առաջադրում «Տեսակավորել զանգվածը ըստ այլ զանգվածի կողմից սահմանված հերթականության» տեսակ առաջին զանգվածը ըստ երկրորդ զանգվածի այնպես, որ առաջին զանգվածում թվերը համեմատաբար դասավորված լինեն 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- ի:

Տեսակավորել զանգվածը ըստ այլ զանգվածի կողմից սահմանված կարգի

 

Gorանգվածը դասավորելու ալգորիթմը `ըստ այլ զանգվածի կողմից սահմանված կարգի

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.

բացատրություն

Մենք տվել ենք երկուսը ամբողջ թիվ զանգվածներ, Հետո մեզ խնդրում են տեսակ առաջին զանգվածը ըստ երկրորդ զանգվածի: Arանգվածներից մեկը պարունակում է այն ամբողջ արժեքները, որոնք պետք է տեսակավորվեն: Իսկ մյուս զանգվածը պարունակում է մի քանի արժեք այն կարգով, որով մենք պետք է տեսակավորենք առաջին զանգվածը: Դա նշանակում է, եթե մենք ունենք երկրորդ զանգվածում տրված թիվը որպես (1, 2, 3, 4): Եվ մենք պետք է փնտրենք բոլոր 1-երը առաջին զանգվածում և դրանք դասակարգված կերպով տեղադրենք առաջին հերթին զանգվածում: Ապա երկրորդ զանգվածում ունենք 2: Գտեք բոլոր զանգվածներից առաջին զանգվածում և դրեք դրանք առաջին շարքում և այլն:

Մենք կօգտագործենք ներկառուցված մեթոդը `ցանկալի արդյունքը պարզելու համար: C ++ - ում մենք կօգտագործենք qsort մեթոդ, qsort մեթոդը նախորոշված ​​մեթոդ է, որն օգտագործվում է որպես quicksort ալգորիթմ: Anyանկացած ցուցակ տեսակավորելու ամենաարագ ալգորիթմներից է: Իսկ java- ում մենք կօգտագործենք Comparator ինտերֆեյսը `զանգվածը ըստ երկրորդ զանգվածի տեսակավորելու համար: Մեթոդը կընտրի արժեքներից երկուսը: Համեմատության համար, և ապա մենք այդ արժեքը կանցկացնենք զանգվածում վայրկյանում որոնման համար: Եթե ​​այն առկա է զանգվածում, երկրորդը առկա է, ապա այն կվերադարձնի ցուցիչը իր երկու արժեքների համար, այն առկա չէ, ապա մենք կվերադարձնենք -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]

Բարդության վերլուծություն

Timeամանակի բարդություն

O (mn Logm) որտեղ «Մ» arr1- ի երկարությունն է & «Ն» arr2- ի երկարությունն է: Քանի որ մենք օգտագործել ենք qsort (տեսակավորման ալգորիթմ): Մենք հասել ենք դրան O (n տեղեկամատյան n) գործոն Այստեղ որոնումը կատարվում է գծային որոնման միջոցով: Եվ դա անելու փոխարեն, մենք կարող էինք հեշտությամբ օգտագործել HashMap, որը ժամանակի բարդությունն էլ ավելի կնվազեցներ:

Տիեզերական բարդություն

O (տեղեկամատյան n), որտեղ «Մ» և «Ն» Arr1- ի և Arr2- ի երկարությունն է: Քանի որ մենք կատարել ենք տեսակավորում ՝ օգտագործելով արագ տեսակավորում, ուստի տարածության բարդությունը դրա պատճառով է: Theրագիրն, ընդհանուր առմամբ, տևում է O (N + M):