क्षुल्लक हॅश फंक्शनचा वापर करून क्रमवारी लावत आहे  


अडचण पातळी मध्यम
वारंवार विचारले कॅडन्स इंडिया Capgemini फॅक्टसेट एमक्यू यूएचजी ऑप्टम
अरे हॅश वर्गीकरण

“क्षुल्लक हॅश फंक्शनचा वापर करून क्रमवारी लावा” ही समस्या सांगते की आपल्याला एक दिले गेले आहे पूर्णांक अॅरे. अ‍ॅरेमध्ये नकारात्मक आणि सकारात्मक दोन्ही असू शकतात. प्रॉब्लेम स्टेटमेंट एरे वापरून सॉर्ट करण्यास सांगते क्षुल्लक हॅश फंक्शन

उदाहरण  

क्षुल्लक हॅश फंक्शनचा वापर करून क्रमवारी लावत आहे

arr[] = {5,2,1,3,6}
{1, 2, 3, 5, 6}
arr[] = {-3, -1, 4, 3, -2, 1, 2, 0}
{-3, -2,-1, 0, 1, 2, 3, 4}

स्पष्टीकरण

सर्व घटक दोन्ही आउटपुटमध्ये सॉर्ट केले आहेत. त्यामुळे आऊटपुट योग्य आहेत.

अल्गोरिदम  

  1. अ‍ॅरेचा कमीतकमी आणि किमान घटक शोधा (किमान घटक परंतु परिपूर्ण मूल्यासह).
  2. आकार जास्तीत जास्त घटक आणि किमान घटकाचे अ‍ॅरे तयार करा.
  3. दोन्ही घटकांची गणना त्यानुसार प्रत्येक घटकासाठी 1 ने वाढवून ती 0 पेक्षा जास्त किंवा 0 पेक्षा कमी असेल तर अनुक्रमे दोन्ही अ‍ॅरेमध्ये संचयित करा.
  4. नकारात्मक घटकांची संख्या असलेल्या अ‍ॅरेचे मुद्रण करा, जसे की तसे घडत नाही. त्याच गोष्टी सकारात्मक घटकासह करा.
  5. आमच्याकडे आहे क्रमवारी लावली रचना.

स्पष्टीकरण

आम्हाला एक दिले जाते अॅरे, त्यात सकारात्मक आणि नकारात्मक पूर्णांक असू शकतात. आमचे कार्य क्षुल्लक हॅश फंक्शनचा वापर करून अ‍ॅरे सॉर्ट करणे. हे सोडवण्यासाठी आम्ही हॅशिंग वापरु आणि दोन अ‍ॅरे सुरू करू. जास्तीत जास्त आणि किमान घटक (परिपूर्ण मूल्यासह किमान घटक) शोधा. एक नकारात्मक घटकांसाठी आहे आणि इतर एक सकारात्मक घटकांसाठी आहे. दोन्ही अ‍ॅरेचे आकार इनपुटच्या जास्तीत जास्त घटकाचे आणि इनपुटच्या नकारात्मक घटकांसारखे असले पाहिजेत परंतु परिपूर्ण मूल्यासह.

हे सुद्धा पहा
बायनरी ट्रीची उंची शोधण्यासाठी Iterative पद्धत

आम्ही दिलेल्या अ‍ॅरेचा मागोवा घेत आहोत आणि अ‍ॅरे घटक 0 पेक्षा जास्त असल्यास अट तपासत आहोत. पॉझिटिव्ह एलिमेंट अ‍ॅरेमध्ये आम्ही त्याची घटना 1 ने वाढवित आहोत आणि जर ती 0 पेक्षा कमी असेल तर याचा अर्थ संख्या नकारात्मक आहे, नकारात्मक घटकांच्या अ‍ॅरेमध्ये त्याची घटना 1 ने वाढवित आहे. ट्रॅव्हर्सल नंतर, आम्ही तयार केलेल्या दोन्ही अ‍ॅरेमध्ये दिलेल्या अ‍ॅरे एलिमेंट्सची संख्या आहे.

आता आपल्याला त्या घटकांना क्रमवारीत प्रिंट करणे आवश्यक आहे. आपण प्रथम नकारात्मक घटकांचा अ‍ॅरे घेऊ, आपल्याला किमान घटकापासून सुरुवात करणे आवश्यक आहे परंतु नकारात्मक चिन्हासह किती वेळा घडते तसे मुद्रित करणे आणि सर्व नकारात्मक मूल्ये मुद्रित केल्याशिवाय मूल्य कमी करणे आवश्यक आहे.

आता 0 पासून प्रारंभ केल्यामुळे, अ‍ॅरेमधील जास्तीत जास्त घटकाची नोंद होईपर्यंत आपण अ‍ॅरेचे सर्व सकारात्मक घटक प्रिंट करू. परंतु आम्हाला हे सुनिश्चित करणे आवश्यक आहे की आम्हाला अ‍ॅरेमध्ये जास्तीत जास्त आणि किमान म्हणून योग्य मूल्य सापडले आहे आणि नकारात्मक चिन्हासह नकारात्मक घटक अ‍ॅरे मूल्य मुद्रित करा किंवा ते -1 ने गुणाकार केल्यानंतर. पूर्ण झाल्यानंतर आम्ही एक सॉर्ट केलेला अ‍ॅरे छापला होता.

क्षुल्लक हॅश फंक्शनचा वापर करून क्रमवारी लावण्यासाठी सी ++ कोड  

#include<iostream>
#include<unordered_map>
#include<algorithm>

using namespace std;

void sortUsingHash(int arr[], int n)
{
    int max = *std::max_element(arr, arr + n);
    int min = abs(*std::min_element(arr, arr + n));

    int positiveNum[max + 1] = { 0 };
    int negativeNum[min + 1] = { 0 };

    for (int i = 0; i < n; i++)
    {
        if (arr[i] >= 0)
            positiveNum[arr[i]] += 1;
        else
            negativeNum[abs(arr[i])] += 1;
    }
    for (int i = min; i > 0; i--)
    {
        if (negativeNum[i])
        {
            for (int j = 0; j < negativeNum[i]; j++)
            {
                cout << (-1) * i << " ";
            }
        }
    }
    for (int i = 0; i <= max; i++)
    {
        if (positiveNum[i])
        {
            for (int j = 0; j < positiveNum[i]; j++)
            {
                cout << i << " ";
            }
        }
    }
}
int main()
{
    int a[] = {7, 5, -4, -3, 2, 4, 1, -2, -1, 0, 6, 3 };

    int n = sizeof(a) / sizeof(a[0]);
    sortUsingHash(a, n);
    return 0;
}
-4 -3 -2 -1 0 1 2 3 4 5 6 7

क्षुल्लक हॅश फंक्शनचा वापर करून सॉर्टिंग करण्यासाठी जावा कोड  

import java.util.Arrays;
class HashingSorting
{
    public static void sortUsingHash(int arr[], int n)
    {
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Math.abs(Arrays.stream(arr).min().getAsInt());

        int positiveNum[] = new int[max + 1];
        int negativeNum[] = new int[min + 1];

        for (int i = 0; i < n; i++)
        {
            if (arr[i] >= 0)
                positiveNum[arr[i]] += 1;
            else
                negativeNum[Math.abs(arr[i])] += 1;
        }
        for (int i = min; i > 0; i--)
        {
            if (negativeNum[i] > 0)
            {
                for (int j = 0; j < negativeNum[i]; j++)
                {
                    System.out.print((-1)*i+" ");
                }
            }
        }
        for (int i = 0; i <= max; i++)
        {
            if (positiveNum[i] > 0)
            {
                for (int j = 0; j < positiveNum[i]; j++)
                {
                    System.out.print(i+" ");
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int a[] = { 7, 5, -4, -3, 2, 4, 1, -2, -1, 0, 6, 3 };
        int n = a.length;
        sortUsingHash(a, n);
    }
}
-4 -3 -2 -1 0 1 2 3 4 5 6 7

गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (कमाल + मिनिट), येथे कमाल इनपुटमधील कमाल आणि किमान घटक आहे. अशा प्रकारे वेळेची जटिलता इनपुटच्या आकारावर अवलंबून नसून त्यातील घटकांवर अवलंबून असते.

हे सुद्धा पहा
दिलेल्या अ‍ॅरेसाठी सर्व अद्वितीय उप-अ‍ॅरेची बेरीज शोधा

स्पेस कॉम्प्लेक्सिटी

ओ (कमाल + मिनिट), येथे कमाल इनपुटमधील कमाल आणि किमान घटक आहे. स्पेस कॉम्प्लेक्सिटी देखील वेळेच्या जटिलतेप्रमाणेच असते, ती इनपुटच्या आकारावर देखील अवलंबून नसते. हे घटकांच्या विशालतेवर अवलंबून असते.