Массивыг өөр массивын тодорхойлсон дарааллын дагуу эрэмбэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Microsoft- SAP лабораторууд Snapchat Yahoo Zoho
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

Тайлбар

А1-ийг А2-ийн дагуу ангилдаг.

Массивыг өөр массивын тодорхойлсон дарааллын дагуу эрэмбэл

 

Массивыг өөр массиваар тодорхойлсон дарааллын дагуу эрэмбэлэх алгоритм

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 арга нь Quicksort алгоритм болгон ашигладаг урьдчилан тодорхойлсон арга юм. Энэ бол аливаа жагсаалтыг эрэмбэлэх хамгийн хурдан алгоритмуудын нэг юм. Мөн 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) хаана "М" arr1 & урт "N" arr2-ийн урт. Бид qsort (ялгах алгоритм) ашигласан тул. Бид хүрсэн O (n log n) хүчин зүйл. Энд хайлтыг шугаман хайлтыг ашиглан хийдэг. Үүнийг хийхийн оронд бид HashMap-ийг хялбархан ашиглаж болох байсан бөгөөд ингэснээр цаг хугацааны нарийн төвөгтэй байдлыг багасгах болно.

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

O (log n), хаана "М" болон "N" нь Arr1 ба Arr2-ийн урт юм. Бид хурдан эрэмбэлэлтийг ашиглан ангилж хийсэн тул орон зайн нарийн төвөгтэй байдал үүнтэй холбоотой юм. Гэхдээ хөтөлбөр бүхэлдээ шаардагдана O (N + M).