დახარისხება ტრივიალური ჰეშის ფუნქციის გამოყენებით


Რთული ტური საშუალო
ხშირად ეკითხებიან კადენს ინდოეთი Capgemini ფაქტები MAQ UHG Optum
Array Hash დახარისხება

პრობლემა "დახარისხება ტრივიალური ჰეშის ფუნქციის გამოყენებით" აცხადებს, რომ თქვენ გეძლევათ მთელი რიცხვი მასივი. მასივი შეიძლება შეიცავდეს როგორც უარყოფით, ასევე დადებით რიცხვებს. პრობლემის დებულება ითხოვს მასივის დალაგებას გამოყენებით ტრივიალური ჰეშის ფუნქცია.

მაგალითი

დახარისხება ტრივიალური ჰეშის ფუნქციის გამოყენებით

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. ჩვენ გვექნება დალაგებულია მასივი

განმარტება

ჩვენ გვაძლევენ მასივი, ეს შეიძლება შეიცავდეს დადებით და უარყოფით რიცხვებს. ჩვენი ამოცანაა მასივის დალაგება Trivial Hash ფუნქციის გამოყენებით. ამის გადასაჭრელად გამოვიყენებთ ჰეშირებას და ორი მასივის ინიციალიზებას. იპოვნეთ მაქსიმალური და მინიმალური ელემენტი (მინიმალური ელემენტი აბსოლუტური მნიშვნელობით). ერთი არის უარყოფითი ელემენტების და მეორე დადებითი ელემენტებისათვის. ორივე მასივის ზომა ტოლი უნდა იყოს შეყვანის მაქსიმალური ელემენტისა და შეყვანის უარყოფითი ელემენტების, მაგრამ აბსოლუტური მნიშვნელობით.

ჩვენ ვათვალიერებთ მოცემულ მასივს და ვამოწმებთ პირობას, თუ მასივის ელემენტი 0-ზე მეტია, ჩვენ გაზრდის მის კლებას 1-ით პოზიტიური ელემენტის მასივში და თუ ის 0-ზე ნაკლებია, ეს ნიშნავს რომ რიცხვი უარყოფითია, ჩვენ უარყოფითი ელემენტის მასივში მისი წარმოქმნა 1-ით იზრდება. გადაკვეთის შემდეგ, ჩვენ თითოეულ მასივში გვაქვს თითოეული მოცემული მასივის ელემენტის რაოდენობა.

ახლა, ჩვენ უნდა დავაბეჭდოთ ეს ელემენტები დახარისხებული წესით. პირველ რიგში ავიღებთ უარყოფითი ელემენტის მასივს, უნდა დავიწყოთ მინიმალური ელემენტიდან, მაგრამ უარყოფითი ნიშნით და დავბეჭდოთ რამდენჯერმე ხდება და ამცირებს მნიშვნელობას, სანამ არ დავამთავრებთ ყველა უარყოფითი მნიშვნელობის დაბეჭდვას.

0-დან დაწყებული, ჩვენ დავბეჭდავთ მასივის ყველა დადებით ელემენტს, რადგან ეს არცერთხელ მოხდება მასივის მაქსიმალურ ელემენტამდე. მაგრამ ჩვენ უნდა დავრწმუნდეთ, რომ მასივში აღმოვაჩინეთ სწორი მნიშვნელობა, როგორც მაქსიმალური და მინიმალური, და მასივის უარყოფითი ელემენტის მნიშვნელობა დავბეჭდეთ უარყოფითი ნიშნით ან -1-ზე გამრავლების შემდეგ დასრულების შემდეგ, ჩვენ დავბეჭდეთ დახარისხებული მასივი.

C ++ კოდი ტორნიალური ჰეშის ფუნქციის გამოყენებით დახარისხების შესასრულებლად

#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

სირთულის ანალიზი

დროის სირთულე

O (მაქს + წთ), აქ მაქსიმალურია შეყვანის მაქსიმალური და მინიმალური ელემენტი. ამრიგად, დროის სირთულე დამოკიდებულია არა შეყვანის ზომაზე, არამედ მის ელემენტებზე.

სივრცის სირთულე

O (მაქს + წთ), აქ მაქსიმალურია შეყვანის მაქსიმალური და მინიმალური ელემენტი. სივრცის სირთულე ასევე იგივეა, რაც დროის სირთულე, ის ასევე არ არის დამოკიდებული შეყვანის ზომაზე. ეს დამოკიდებულია ელემენტების სიდიდეზე.