一个偶然想到的算法,其它题解中不曾写过的,或许将会有什么用处。
算法
(Trie) $O(n \log a _ i)$
- 将所有数据按二进制从高位到低位扔到一棵
Trie
中, - 从
Trie
的根开始,按字典序遍历整棵树并输出
复杂度分析
一共会在 Trie
中插入 $n$ 个数,
那么一共就会在 Trie
中开 $\sum \log a _ i$ 个节点,
每开一个节点的复杂度是 $O(1)$ 的,遍历整棵树的复杂度也取决于节点数,
所以总时间复杂度是 $O(\sum \log a _ i) = O(n \log a _ i)$。
空间复杂度也是 $O(n \log a _ i)$。
C++ 代码
#include <cstdio>
#include <cstring>
const int N = 100005;
const int M = 3100005;
int n, x;
int tr[M][2], cnt[M], idx;
void insert()
{
int p = 0;
// 由于 a[i] 最大是 10 ^ 9,所以这里从 29 位开始遍历即可
// 代码中从 30 位开始遍历是为了方便输出
for (int i = 30; ~i; i -- )
{
int u = x >> i & 1;
if (!tr[p][u]) tr[p][u] = ++idx;
p = tr[p][u];
}
cnt[p] ++ ;
}
// u 表示当前节点,x 表示当前值,k 表示当前位数
void write(int u, int x, int k)
{
if (tr[u][0]) write(tr[u][0], x, k - 1); // 处理该位是 0 的情况
if (tr[u][1]) write(tr[u][1], x | 1 << k, k - 1); // 处理该位是 1 的情况
while (cnt[u] -- ) printf("%d ", x); // 如果 cnt 不为 0,那么输出 cnt 次当前的数
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &x);
insert();
}
// 因为插入是从第 30 位开始的,所以这里直接从 tr[0][0] 开始处理后面 29 位即可
write(tr[0][0], 0, 29);
return 0;
}
《抽风排序》
《关于trie的抽风排序》(trie是什么鬼)
抽风排序的要笑死我,hh
秀啊
思想有点像基数排序?(
对,超像鸡排,但我想到这个的灵感是源于最大异或对那题QwQ
然后我今天发现这玩意可以快速将一堆字符串排序(虽然并没有题会让你把一堆字符串排序
但是如果要排序一堆字符串的话就不是log级别了吧
对如果一堆字符串会比
sort
快不少,但是空间复杂度可能会炸