अर्को एर्रे द्वारा परिभाषित क्रम अनुसार एर्रे क्रमबद्ध गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन माइक्रोसफ्ट SAP ल्याबहरू Snapchat याहू Zoho
एरे खोजी क्रमबद्ध

समस्या वक्तव्य

तपाईंलाई दुई दिइयो एर्रेहरू of पूर्णांकहरू arr1 [] र arr2 []। समस्या "अर्को एर्रे द्वारा परिभाषित अर्डर अनुसार एर्रे क्रमबद्ध गर्नुहोस्" सोध्छ भाग्य पहिलो एर्रे दोस्रो एर्रेको आधारमा ताकि एर्रेमा अ relatively्क तुलनात्मक रूपमा सबै मानहरू क्रमबद्ध गरीनेछ। []। र पहिलो एर्रेमा एलिमेन्टहरू जुन दोस्रो एर्रेमा छैनन् एर्रेको अन्त्यमा क्रमबद्ध ढ in्गले घुसाइनेछ।

उदाहरणका

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.

स्पष्टीकरण

हामीले दुई दिएका छौं पूर्णांक एर्रेहरू। त्यसोभए हामीलाई सोधिन्छ भाग्य दोस्रो एर्रेको अनुसार पहिलो एर्रे। एउटा एर्रेमा सम्पूर्ण मानहरू समावेश छ जुन क्रमबद्ध गर्नु पर्ने हुन्छ। र अन्य एर्रेमा केहि कम मूल्यहरू समावेश छ हामीले पहिलो एरे क्रमबद्ध गर्नुपर्दछ। यसको मतलब यदि हामीसँग दोस्रो एर्रेमा दिइएको नम्बर छ (१, २,,,))। र हामीले पहिलो एर्रेमा सबै १ हरू खोज्नु पर्छ र तिनीहरूलाई क्रमबद्ध ढंगमा पहिले एर्रेमा राख्नु पर्छ। त्यसपछि हामीसंग दोस्रो एरेमा २ छ। सबै एर्रेलाई पहिलो एर्रेमा फेला पार्नुहोस् र त्यसपछि तिनीहरूलाई पहिलो एर्रेमा राख्नुहोस् र यस्तै।

हामी इच्छित परिणाम पत्ता लगाउन इनबिल्ट विधि प्रयोग गर्ने छौं। C ++ मा हामी यो प्रयोग गर्दैछौं qsort विधि, क्यूसोर्ट विधि एक पूर्वनिर्धारित विधि हो जुन क्विकोर्ट एल्गोरिथ्मको रूपमा प्रयोग हुन्छ। कुनै पनि सूची क्रमबद्ध गर्न यो सब भन्दा छिटो एल्गोरिदम हो। र जाभामा, हामी कम्पेरेटर इन्टरफेस प्रयोग गरीरहेछौं एर्रेलाई दोस्रो एर्रेको आधारमा क्रमबद्ध गर्न। विधिले दुई मानहरू छान्छ। तुलनाको लागि, र त्यसपछि हामी एरे दोस्रोमा खोजीको लागि त्यो मानलाई पास गर्नेछौं। यदि यो एर्रेमा उपस्थित छ भने दोस्रो હાજર छ भने यसले यसको दुबै मानको लागि अनुक्रमणिका फर्काउँछ, यो अवस्थित छैन, तब हामी मान -१ फिर्ता गर्नेछौं।

हामीले केहि सर्तहरू बनाएका छौं। यदि हामीले दुबै फर्काइएका मानहरू सकारात्मकका रूपमा भेट्यौं भने। त्यसो भए फर्केका मानहरूको भिन्नता फिर्ता गर्छौं यदि मात्र पहिलो मान यदि सकारात्मक छ भने फिर्ता -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]

जटिलता विश्लेषण

समय जटिलता

O (mn Logm) जहाँ "M" arr1 को लम्बाई हो र "N" एआर २ को लम्बाई हो। हामीले क्युसोर्ट (छँटाई एल्गोरिथ्म) प्रयोग गर्यौं। हामीले हासिल गरेका छौं O (n log n) कारक यहाँ खोजी लाइनर खोजको प्रयोग गरी गरिन्छ। र त्यसो गर्नुको सट्टा, हामीले सजिलै ह्याशम्याप प्रयोग गर्न सक्थ्यौं जसले समयको जटिलतालाई अझ कम गर्थ्यो।

ठाउँ जटिलता

O (लग एन), जहाँ "M""N" Arr1 र Arr2 को लम्बाई हो। किनकि हामीले छिटो क्रमबद्ध गरेर क्रमबद्ध गरेका छौं त्यसैले अन्तरिक्ष जटिलता यसको कारण हो। तर सम्पूर्ण कार्यक्रम लिन्छ O (N + M)