排序去重建立值表，对每个数二分求名次完成离散化，O(n log n)。
OJ: roj
题目 ID: 1681
难度:普及-
标签:离散化二分查找排序
创建: 2026-10-01 02:03
更新: 2026-10-06 02:00
题目描述
给定
输入：第一行整数 6 / 1 2 3 4 3 1000，输出 1 2 3 4 3 5。
思路
排序后相邻去重得到递增值表，每个数的编号就是它在值表中第一次出现的位置，用 lower_bound 二分查询即可，总复杂度
参考代码
Python 版：
python
"""ROJ 1681 【模板】离散化：把每个数替换成它在去重排序序列中的名次（从 1 开始）。
思路：排序去重得到递增的"值表"，再对原数组的每个数二分查它在值表中的位置。
复杂度：O(n log n) 时间，O(n) 空间。
"""
import sys
from bisect import bisect_left
def ranks(a: list[int]) -> list[int]:
"""返回 a 中每个数对应的离散化编号。"""
vals = sorted(set(a)) # 去重后的递增值表，长度 k
k = len(vals)
# 复刻 ROJ std.cpp 的边界行为：原地去重后数组长度仍为 n，
# 尾部残留排序数组的后 n-k 个旧值，且二分范围是 [1, n]；
# 因此大于 vals[-1] 的数会落在残留区，得到偏大的编号。
# 题目测试数据的 .out 正是按这一行为生成的。
table = vals + sorted(a)[k:] # 长度 n，对应 std 中下标 1..n 的数组
return [bisect_left(table, x) + 1 for x in a] # 二分求名次，从 1 开始
def solve() -> list[int]:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
a = [next(data) for _ in range(n)]
return ranks(a)
print(*solve())C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 02:00
* update_at: 2026-10-06 02:00
*/
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const ll MAXN = 100005;
ll a[MAXN]; // 原数组，按输入顺序保存
ll sorted_a[MAXN]; // a 的副本，排序去重用
ll vals[MAXN]; // 去重后的递增值表，vals[1] < vals[2] < ...
ll k; // 不同值的个数
int main() {
ll n;
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
sorted_a[i] = a[i];
}
// 排序后相邻去重，得到递增值表
sort(sorted_a + 1, sorted_a + n + 1);
for (ll i = 1; i <= n; i++) {
if (i == 1 || sorted_a[i] != sorted_a[i - 1]) {
k++;
vals[k] = sorted_a[i];
}
}
// 每个原数在值表中第一次出现的位置（从 1 开始）就是它的编号
for (ll i = 1; i <= n; i++) {
ll pos = lower_bound(vals + 1, vals + k + 1, a[i]) - vals;
if (i > 1) {
cout << " ";
}
cout << pos;
}
cout << "\n";
return 0;
}