Сортировка с использованием тривиальной хеш-функции


Сложный уровень средний
Часто спрашивают в Cadence Индия Capgemini Набор фактов MAQ UHG Optum
массив 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

Код 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 - это максимальный и минимальный элемент во входных данных. Сложность пространства такая же, как и сложность времени, она также не зависит от размера ввода. Это зависит от величины элементов.