Сартаванне з выкарыстаннем трывіяльнай хэш-функцыі


Узровень складанасці серада
Часта пытаюцца ў Cadence Індыя Capgemini Факты MAQ UHG Optum
масіў гашыш сартаванне

Праблема «Сартаванне з выкарыстаннем трывіяльнай хэш-функцыі» абвяшчае, што вам дадзена цэлае масіў. Масіў можа ўтрымліваць як адмоўныя, так і дадатныя лікі. Пастаноўка праблемы просіць сартаваць масіў з дапамогай Трывіяльная хэш-функцыя.

Прыклад

Сартаванне з выкарыстаннем трывіяльнай хэш-функцыі

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

Код Java для сартавання з выкарыстаннем трывіяльнай хэш-функцыі

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 (макс. + Мін.), тут max - максімальны і мінімальны элемент уваходных дадзеных. Такім чынам, складанасць часу залежыць не ад памеру ўваходных дадзеных, а ад яго элементаў.

Касмічная складанасць

O (макс. + Мін.), тут max - максімальны і мінімальны элемент уваходных дадзеных. Касмічная складанасць таксама такая ж, як і складанасць часу, яна таксама не залежыць ад памеру ўваходных дадзеных. Гэта залежыць ад велічыні элементаў.