トリビアルハッシュ関数を使用した並べ替え


難易度 ミディアム
よく聞かれる ケイデンスインド キャップジェミニ ファクトセット MAQ UHGオプタム
配列 ハッシュ 並べ替え(ソート)

「トリビアルハッシュ関数を使用したソート」の問題は、 整数 配列。 配列には、負の数と正の数の両方を含めることができます。 問題ステートメントは、を使用して配列をソートするように要求します 些細なハッシュ関数。

トリビアルハッシュ関数を使用した並べ替え

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. 私たちは ソート アレイ。

説明

私たちは与えられます 配列、正と負の整数を含めることができます。 私たちのタスクは、トリビアルハッシュ関数を使用して配列をソートすることです。 これを解決するために、ハッシュを使用してXNUMXつの配列を初期化します。 最大要素と最小要素(絶対値を持つ最小要素)を見つけます。 XNUMXつは負の要素用で、もうXNUMXつは正の要素用です。 両方の配列のサイズは、入力の最大要素と入力の負の要素に等しくなければなりませんが、絶対値を使用します。

与えられた配列をトラバースし、配列要素が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は、入力の最大要素と最小要素です。 空間の複雑さも時間の複雑さと同じであり、入力のサイズにも依存しません。 それは要素の大きさに依存します。