அற்பமான ஹாஷ் செயல்பாட்டைப் பயன்படுத்தி வரிசைப்படுத்துதல்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது காடென்ஸ் இந்தியா கேப்ஜெமினி உண்மை MAQ யுஎச்ஜி ஆப்டம்
அணி ஹாஷ் வரிசையாக்க

"அற்பமான ஹாஷ் செயல்பாட்டைப் பயன்படுத்தி வரிசைப்படுத்துதல்" என்ற சிக்கல் உங்களுக்கு வழங்கப்பட்டுள்ளது என்று கூறுகிறது முழு வரிசை. ஒரு வரிசை எதிர்மறை மற்றும் நேர்மறை எண்களைக் கொண்டிருக்கலாம். சிக்கல் அறிக்கை வரிசை பயன்படுத்தி வரிசைப்படுத்த கேட்கிறது அற்பமான ஹாஷ் செயல்பாடு.

உதாரணமாக

அற்பமான ஹாஷ் செயல்பாட்டைப் பயன்படுத்தி வரிசைப்படுத்துதல்

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. எங்களுக்கு இருக்கும் வரிசைப்படுத்தப்பட்ட வரிசை.

விளக்கம்

எங்களுக்கு ஒரு வழங்கப்படுகிறது வரிசை, இது நேர்மறை மற்றும் எதிர்மறை முழு எண்களைக் கொண்டிருக்கலாம். ட்ரிவல் ஹாஷ் செயல்பாட்டைப் பயன்படுத்தி வரிசையை வரிசைப்படுத்துவதே எங்கள் பணி. இதைத் தீர்க்க நாம் ஹேஷிங்கைப் பயன்படுத்துவோம், இரண்டு வரிசைகளைத் தொடங்குவோம். அதிகபட்ச மற்றும் குறைந்தபட்ச உறுப்பைக் கண்டறியவும் (முழுமையான மதிப்பைக் கொண்ட குறைந்தபட்ச உறுப்பு). ஒன்று எதிர்மறை கூறுகளுக்கும் மற்றொன்று நேர்மறை கூறுகளுக்கும். இரண்டு வரிசைகளின் அளவு உள்ளீட்டின் அதிகபட்ச உறுப்பு மற்றும் உள்ளீட்டின் எதிர்மறை கூறுகளுக்கு சமமாக இருக்க வேண்டும், ஆனால் முழுமையான மதிப்புடன் இருக்க வேண்டும்.

கொடுக்கப்பட்ட வரிசைக்கு நாம் பயணிப்போம், ஒரு வரிசை உறுப்பு 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (அதிகபட்சம் + நிமிடம்), இங்கே அதிகபட்சம் உள்ளீட்டில் அதிகபட்ச மற்றும் குறைந்தபட்ச உறுப்பு ஆகும். இதனால் நேர சிக்கலானது உள்ளீட்டின் அளவைப் பொறுத்து அல்ல, ஆனால் அதன் கூறுகளைப் பொறுத்தது.

விண்வெளி சிக்கலானது

ஓ (அதிகபட்சம் + நிமிடம்), இங்கே அதிகபட்சம் உள்ளீட்டில் அதிகபட்ச மற்றும் குறைந்தபட்ச உறுப்பு ஆகும். விண்வெளி சிக்கலானது நேர சிக்கலானதைப் போன்றது, இது உள்ளீட்டின் அளவைப் பொறுத்தது அல்ல. இது தனிமங்களின் அளவைப் பொறுத்தது.