Сортування за допомогою тривіальної хеш-функції


Рівень складності Medium
Часто запитують у Каденс Індія 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. Після завершення ми надрукували відсортований масив.

Код С ++ для здійснення сортування за допомогою тривіальної хеш-функції

#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 - це максимальний та мінімальний елемент вводу. Складність простору така ж, як і складність часу, вона також не залежить від розміру вхідних даних. Це залежить від величини елементів.