C++でハッシュ（unordered_map）を使って配列を縮小形式に変換する方法

このチュートリアルでは、ハッシュ（連想配列）を活用して、配列を縮小形式（reduced form）に変換するC++のプログラムについて解説します。

縮小形式への変換とは、与えられた配列の要素を、元の大小関係（相対的な順序）を保ったまま 0 ～ n-1 の範囲の値に置き換える処理のことです。例えば、配列 {10, 20, 15, 12, 11, 50} の場合、最も小さい要素「10」は「0」に、次に小さい「11」は「1」に、というように各要素をその順位へと変換します。

アルゴリズムの流れ

1. 元の配列をコピーし、昇順にソートします。
2. ソート済みの各要素に対して、0 から始まる順位を割り当て、「要素 → 順位」のペアとして unordered_map（ハッシュテーブル）に格納します。
3. 元の配列の各要素を、ハッシュテーブルから取得した順位で上書きします。

ハッシュテーブルを使うことで、各要素の順位を O(1) で高速に参照できるのがポイントです。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 配列を縮小形式に変換する関数
void convert(int arr[], int n){
    // 配列の要素をコピーしてソート
    int temp[n];
    memcpy(temp, arr, n*sizeof(int));
    sort(temp, temp + n);
    // ハッシュテーブル（unordered_map）を作成
    unordered_map<int, int> umap;
    int val = 0;
    for (int i = 0; i < n; i++)
        umap[temp[i]] = val++;
    // 元の配列の要素をハッシュテーブルの値で置き換え
    for (int i = 0; i < n; i++)
        arr[i] = umap[arr[i]];
}
void print_array(int arr[], int n) {
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
int main(){
    int arr[] = {10, 20, 15, 12, 11, 50};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Given Array :\n";
    print_array(arr, n);
    convert(arr , n);
    cout << "\nConverted Array:\n";
    print_array(arr, n);
    return 0;
}

実行結果

Given Array :
10 20 15 12 11 50
Converted Array:
0 4 3 2 1 5

計算量について

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(n log n) です。ハッシュテーブルへの登録と参照はそれぞれ平均 O(n)、O(1) で行えるため、全体のボトルネックにはなりません。また、補助配列とハッシュテーブルの分だけ余分なメモリが必要となり、空間計算量は O(n) となります。