离散化

排序算法的一个应用是离散化，离散化即把无穷大集合中的若干个元素映射为有限集合以便于统计的方法，实现离散化一般有两种方式：

• 数组，排序去重

vector<int> all; // 存储所有待离散化的值
sort(all.begin(), all.end()); // 排序
alls.erase(unique(all.begin(), all.end()), all.end());   // 去重

// 二分求出x对应的离散化的值, 即离散数组的下标
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = all.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (all[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到 1, 2, ...n
}

• Map

unordered_map<int, int> mp;
int idx = 0;
for (auto &x : nums) {
  if (!mp.count(x)) mp[x] = ++idx; // 映射到 1, 2, ...n
}

// 求离散化后的值
mp[x];

解法一：离散化

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 2e5 + 7;

int n, m;
vector<int> all;
int p[3*N];
int a[N], b[N], c[N];

int find(int x) {
    int l = 0, r = all.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (all[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        all.push_back(a[i]);
    }
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
        all.push_back(b[i]);
    }
    for (int i = 0; i < m; ++i) {
        cin >> c[i];
        all.push_back(c[i]);
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());

    for (int i = 0; i < n; ++i) {
        ++p[find(a[i])];
    }
    int maxb = 0;
    for (int i = 0; i < m; ++i) {
        maxb = max(maxb, p[find(b[i])]);
    }
    int maxc = 0, ans = -1;
    for (int i = 0; i < m; ++i) {
        int idx = find(c[i]);
        if (p[find(b[i])] == maxb && p[idx] > maxc) maxc = p[idx], ans = i + 1; 
    }
    cout << ans;
    return 0;
}

离散化需要将所有值先收集起来，时间接近极限，可能会 TLE

解法二：unordered_map

这里不再用 map 进行离散化，直接统计即可

#include <iostream>
#include <unordered_map>
using namespace std;

const int N = 2e5 + 7;

unordered_map<int, int> mp;
int n, m;
int b[N];

int main() {
    cin >> n;
    int x;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        ++mp[x];
    }
    cin >> m;
    int maxb = 0;
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
        if (mp[b[i]] > maxb) maxb = mp[b[i]];
    }
    int maxc = -1, ans;
    for (int i = 0; i < m; ++i) {
        cin >> x;
        if (mp[b[i]] == maxb && mp[x] > maxc) maxc = mp[x], ans = i + 1; 
    }
    cout << ans;
    return 0;

}