座標圧縮

init

• 数列\(A\)を与えると、クラスを\(A\)で初期化する
• このとき、\(A\)の全ての\(2\)つの要素について大小関係が維持され、かつindexの最大値が最小になるように\(A\)の各要素にindexという非負整数が割り振られる
• 計算量は\(N=\vert A \vert\)とし、\(Ο(NlogN)\)

compress

• コンストラクタ。initを呼ぶ

size

• initで与えられた数列の中に含まれる値の種類数を返す
• 計算量は\(Ο(1)\)

index

• 値を与えると、その値に対応するindexを返す
• もし数列に存在しない値が与えられたら、数列に存在する値の中で、与えられた値より小さい最大の値についてのindexを返す(つまり、小さい値に寄せる)
• もし列のいかなる値よりも小さければ\(-1\)を返す
• 計算量はinitの\(N\)を用いて、\(Ο(logN)\)

value

• indexを与えると値を返す
• 範囲外なら\(0\)を返す
• 計算量は\(Ο(1)\)

github

class compress{
    // Copyright (c) 2023 0214sh7
    // https://github.com/0214sh7/library/
    private:
    std::vector<int> E;
    
    public:
    void init(std::vector<long long> A){
        E.clear();
        sort(A.begin(),A.end());
        for(int i=0;i<A.size();i++){
            if(i==0 || A[i]!=A[i-1]){
                E.push_back(A[i]);
            }
        }
    }
    
    compress(std::vector<long long> A){
        init(A);
    }
    
    int size(){
        return (int)E.size();
    }
    
    int value(int x){
        if(0<=x && x<(int)E.size()){
            return E[x];
        }else{
            return 0;
        }
    }
    
    int index(int X){
        return (upper_bound(E.begin(),E.end(),X))-E.begin()-1;
    }
    
};

使用例

---

実行コード

#include <bits/stdc++.h>

class compress{/*省略*/};

int main(void){
    
    std::vector<long long> A={1,2,4,8,16,32,64,128};
    compress zaatsu(A);
    
    std::cout << "uniqueな要素の個数" << std::endl;
    std::cout << zaatsu.size() << std::endl;
    std::cout << std::endl;
    
    std::cout << "Aの各要素に対応する数" << std::endl;
    for(int i=0;i<A.size();i++){
        std::cout << zaatsu.index(A[i]) << " ";
    }
    std::cout << std::endl << std::endl;
    
    std::cout << "0~7に対応する要素" << std::endl;
    for(int i=0;i<zaatsu.size();i++){
        std::cout << zaatsu.value(i) << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

出力

uniqueな要素の個数
8

Aの各要素に対応する数
0 1 2 3 4 5 6 7 

0~7に対応する要素
1 2 4 8 16 32 64 128 

更新履歴

---

日時	内容
2023/06/29	ライセンスのコメントアウトを変更
2021/03/26	使用例、コンストラクタを追加
2020/05/20	mapで処理しvectorで返す形式から、class化し二分探索を行う形式に変更
2020/04/05	座標圧縮を追加