離散化

離散化

如果資料要存入陣列，資料數字範圍極大，但並非連續。
也就是數學中的「標準化」

P-2-2. 離散化 – sort

題目：https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a140

假設有 N 個整數要被讀到一個陣列中，我們想要將這些整數置換成從 0 開始依序排列的整數並且維持它們原來的大小關係，例如輸入的整數序列是 (5, 3, 9, 3, 15, 9, 8, 9)，這些數如從小到大排是 ( 3, 3, 5, 8, 9, 9, 9, 15)，去 除重複者後為(3, 5, 8, 9, 15)，所以我們要替換的是：
3 → 0
5 → 1
8 → 2
9 → 3
15 → 4

所以原先的序列就會變成(1, 0, 3, 0, 4, 3, 2, 3)。
Time limit: 1 秒
輸入格式：輸入兩行，第一行是正整數 N，N 不超過 10 萬，第二行是 N 個整數，大 小不超過 109，以空白間隔。
輸出：輸出置換後的序列，兩數之間以一個空白間隔。

範例輸入： 7 0 3 9 3 3 -1 0
範例輸出： 1 2 3 2 2 0 1

1.純陣列法

code

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define nn "\n"

bool cmp(pii a, pii b){
    return a.first<b.first;
}

int main(){
    //istringstream cin("7 \
0 3 9 3 3 -1 0");

    vector<pii>v;

    int n;
    cin>>n;
    v.resize(n);//0~6
    for(int i=0;i<n;i++){
        cin>>v[i].first;
        v[i].second=i;
    }

    // for(pii i:v){
    //     cout<<i.first<<" ";
    // }cout<<nn;

    sort(all(v),cmp);


    // for(pii i:v){
    //     cout<<i.first<<" ";
    // }cout<<nn;

    vector<int>ans(n);

    int it=-1;
    int pr=INT_MAX;
    for(int i=0;i<n;i++){
        if(v[i].first!=pr){
            pr=v[i].first;
            it++;
        }
        ans[v[i].second]=it;
    }
    for(int i:ans){
        cout<<i<<" ";
    }
}

expandcollapse

2.運用map

code

#include <bits/stdc++.h>
using namespace std;
#define N 100001

int main(){
    int n;
    cin>>n;
    int v[N];
    map<int,int>mp;
    
    //存v、在mp中放置
    for(int i=0;i<n;i++){
        cin>>v[i];
        mp[v[i]];
    }

    //為mp的每個second重新編號
    int w=0;
    for(auto &it:mp){
        it.second=w;
        w++;
    }

    //依照每個v[i]輸出
    for(int i=0;i<n;i++){
        cout<<mp[v[i]]<<" ";
    }
}

expandcollapse

看完兩種解法
誰比較快呢？

純陣列法較快，因為排序速度一樣，而遍歷陣列比set來的快

陣列、更好寫的方法(from IONC)

code

//IONC做法
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dis_bs(vector<int>& arr) {
    vector<int> tmp = arr;

    // 對tmp中的元素進行排序
    sort(tmp.begin(), tmp.end());

    // 去除tmp中的重複元素
    tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());

    // 對arr中的每個元素進行操作
    for(int i = 0; i < arr.size(); i++)
        // 使用lower_bound找到arr[i]在tmp中的位置，並將其轉換為離散化後的值
        arr[i] = lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin() ;
}

int main() {

    int n;
    cin>>n;
    vector<int> arr(n);
    for(int &i:arr){
        cin>>i;
    }
    dis_bs(arr);

    // 輸出離散化後的結果
    for(int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

expandcollapse