በሌላ ድርድር በተገለጸው ቅደም ተከተል መሠረት አንድ ድርድርን ደርድር


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን የ Microsoft የ SAP ላብራቶሪዎች Snapchat ያሁ ቮሆ
ሰልፍ በመፈለግ ላይ መደርደር

የችግሩ መግለጫ

ሁለት ተሰጥተሃል ድርድሮች of ኢንቲጀሮች arr1 [] እና arr2 []. ችግሩ “በሌላ ድርድር በተገለጸው ቅደም ተከተል መሠረት አንድ ድርድርን ይመድቡ” የሚለው ጥያቄ ይጠይቃል ዓይነት የመጀመሪያው ድርድር በሁለተኛው ድርድር መሠረት በመጀመሪያ ድርድር ላይ ያሉት ቁጥሮች በአራ 2 [] ውስጥ ያሉትን እሴቶች በአንጻራዊነት እንዲመጣጠኑ ይደረጋል ፡፡ እና በሁለተኛው ድርድር ውስጥ የሌሉት በመጀመሪያው ድርድር ውስጥ ያሉት ንጥረ ነገሮች በድርድሩ መጨረሻ ላይ በተስተካከለ መንገድ እንዲገቡ ይደረጋል።

ለምሳሌ

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 ዘዴ እንደ ፈጣን የመለዋወጥ ስልተ ቀመር ጥቅም ላይ የዋለ አስቀድሞ የተቀመጠ ዘዴ ነው። ማንኛውንም ዝርዝር ለመደርደር በጣም ፈጣኑ ስልተ ቀመር አንዱ ነው። እና በጃቫ ውስጥ ድርድርን በሁለተኛው ድርድር መሠረት ለመደርደር የንፅፅር በይነገጽን እንጠቀማለን ፡፡ ዘዴው ሁለት እሴቶችን ይመርጣል። ለማነፃፀር እና ከዚያ በድርድር ሰከንድ ውስጥ ለመፈለግ ያንን እሴት እናስተላልፋለን ፡፡ በድርድር ሰከንድ ውስጥ የሚገኝ ከሆነ ከዚያ ለሁለቱም እሴቶች መረጃ ጠቋሚውን ይመልሳል ፣ አይገኝም ፣ ከዚያ እሴቱን እንመልሳለን -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

በሌላ ድርድር በተገለጸው ቅደም ተከተል መሠረት ድርድርን ለመደርደር የጃቫ ኮድ

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]

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (mn Logm) የት "M" የ arr1 & ርዝመት ነው “N” የ arr2 ርዝመት ነው። እኛ qsort ን ስለተጠቀምን (ስልተ ቀመርን መለየት)። እኛ አሳክተናል ኦ (n log n) ምክንያት እዚህ ፍለጋው የሚከናወነው መስመራዊ ፍለጋን በመጠቀም ነው። እናም ያንን ከማድረግ ይልቅ የጊዜ ውስብስብነቱን የበለጠ የሚቀንስ ሃሽማፕን በቀላሉ ልንጠቀም እንችላለን ፡፡

የቦታ ውስብስብነት

ኦ (ምዝግብ ማስታወሻ n) ፣ የት "M"“N” የ Arr1 እና Arr2 ርዝመት ነው። ምክንያቱም ፈጣን ድርድርን በመጠቀም መደርደርን ስለሠራን የቦታ ውስብስብነት በዚያ ምክንያት ነው ፡፡ ግን ፕሮግራሙ በአጠቃላይ ይወስዳል ኦ (N + M)