एक सरणी को दूसरे सरणी द्वारा परिभाषित क्रम के अनुसार क्रमबद्ध करें


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना माइक्रोसॉफ्ट एसएपी लैब्स Snapchat याहू Zoho
ऐरे खोजना छंटाई

समस्या का विवरण

आपको दो दिए जाते हैं सरणियों 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) है। और हमें पहले सरणी में सभी 1s को खोजना होगा और उन्हें पहले सरणी में पहले क्रमबद्ध तरीके से डालना होगा। फिर हमारे पास दूसरे एरे में 2 हैं। पहले सरणी में सभी 2s का पता लगाएं और फिर उन्हें पहले सरणी और इतने पर रखें।

हम वांछित परिणाम का पता लगाने के लिए इनबिल्ट विधि का उपयोग करेंगे। C ++ में, हम इसका उपयोग करेंगे क्यूसोर्ट विधि, qsort विधि एक पूर्वनिर्धारित विधि है जिसका उपयोग क्विकसॉर्ट एल्गोरिथम के रूप में किया जाता है। यह किसी भी सूची को क्रमबद्ध करने के लिए सबसे तेज़ एल्गोरिदम में से एक है। और जावा में, हम दूसरे सरणी के अनुसार सरणी को सॉर्ट करने के लिए तुलनित्र इंटरफ़ेस का उपयोग करेंगे। विधि दो मानों को चुनेगी। तुलना के लिए, और फिर हम सरणी दूसरी में खोज करने के लिए उस मान को पास करेंगे। यदि यह एक सरणी में मौजूद है दूसरा मौजूद है तो यह अपने दोनों मूल्यों के लिए सूचकांक लौटाएगा, यह मौजूद नहीं है, फिर हम मान -1 वापस करेंगे।

हमने कुछ शर्तें बनाई हैं। यदि हम लौटे हुए दोनों मानों को सकारात्मक मानते हैं। फिर हम लौटे हुए मूल्यों का अंतर वापस करते हैं। यदि केवल पहला मान यदि सकारात्मक है तो -1 लौटाएं। और यदि केवल दूसरा मान धनात्मक है, तो वापस लौटें। 1. यदि कोई भी शर्त पूरी नहीं होती है, तो पहले दिए गए मान से चुने गए मानों का अंतर वापस कर दें। सभी तुलना के बाद, सरणी को सॉर्ट किया जाएगा। अंत में सॉर्ट किए गए सरणी को प्रिंट करें।

कोड

सी ++ कोड एक सरणी को दूसरे सरणी द्वारा परिभाषित क्रम के अनुसार क्रमबद्ध करने के लिए

#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 (एमएन लोगम) जहां "एम" arr1 की लंबाई है & "N" arr2 की लंबाई है। चूंकि हमने qsort (सॉर्टिंग एल्गोरिदम) का उपयोग किया है। हमने हासिल किया है ओ (एन लॉग एन) कारक। यहां खोज रैखिक खोज का उपयोग करके की जाती है। और ऐसा करने के बजाय, हम आसानी से एक HashMap का उपयोग कर सकते थे जिसने समय की जटिलता को और भी कम कर दिया होगा।

अंतरिक्ष जटिलता

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