计数时怎样避免每个元素查两次哈希表，Array.Sort 从哪个输入规模开始不再保持相等元素的原有顺序，以及 C# 直到 .NET 6 才有的堆，很多老的 C# 竞赛代码至今还在绕开它。
这一篇讲容器，也讲 C# 标准库里竞赛题解常常写错的那些部分，因为那些题解写成时，这些功能还没出现。
下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果里粘贴过来。
模式 26 — 计数
四种写法，按开销从小到大排列。
using System.Runtime.InteropServices;
int[] a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
// The version everyone writes. Two hash lookups per item.
Dictionary<int, int> plain = [];
foreach (int x in a) plain[x] = plain.GetValueOrDefault(x) + 1;
// One lookup. The ref points into the dictionary's own storage.
Dictionary<int, int> fast = [];
foreach (int x in a)
{
ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(fast, x, out _);
slot++;
}
// .NET 9 and later. Shortest to write, allocates an enumerable.
var counted = a.CountBy(x => x).OrderBy(kv => kv.Key);
Console.WriteLine($"plain : {string.Join(" ", plain.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"ref : {string.Join(" ", fast.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"CountBy : {string.Join(" ", counted.Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"all agree: {plain.OrderBy(k => k.Key).SequenceEqual(fast.OrderBy(k => k.Key))}");
// When the keys are small and dense, skip hashing altogether.
int[] tally = new int[10];
foreach (int x in a) tally[x]++;
Console.WriteLine($"array : [{string.Join(", ", tally)}] <- no hashing at all");输出：
plain : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
ref : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
CountBy : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
all agree: True
array : [0, 2, 1, 2, 1, 3, 1, 0, 0, 1] <- no hashing at alldict[x] = dict.GetValueOrDefault(x) + 1 会把键哈希两次：读一次，写一次。CollectionsMarshal.GetValueRefOrAddDefault 直接返回一个指向字典内部存储的 ref，所以只查一次，就能原地加一。在遍历一百万个元素的紧凑循环里，这个差别是实打实的，而且只要三行。
CountBy 从 .NET 9 开始提供。它写起来最短，但会分配一个可枚举对象。不在热点循环里的话，这个取舍是对的。
如果键是较小的非负整数，一个普通的 int[] 比上面几种都快。不用哈希，没有冲突，内存连续。如果题目说值在 1 到 10⁶ 之间，这个数组占 4MB，而它几乎肯定就是正解。
适用场景： 随时都用得上，关键是选对写法。键小而密集，用数组。热点循环，用 ref。其他情况，写最好读的那种。
模式 27 — 按签名分组
把互为字母异位词的单词分到一组。
这个模式的全部内容就是选一个签名：同组内所有元素的签名都相同，组外的元素都不同。
string[] words = ["eat", "tea", "tan", "ate", "nat", "bat"];
// The signature has to be identical for anagrams and different for anything
// else. Sorted letters is the obvious one.
static string SortedKey(string w)
{
char[] c = w.ToCharArray();
Array.Sort(c);
return new string(c);
}
// For a fixed alphabet, a count vector is O(n) instead of O(n log n).
static string CountKey(string w)
{
int[] n = new int[26];
foreach (char c in w) n[c - 'a']++;
return string.Join(",", n);
}
foreach (var g in words.GroupBy(SortedKey))
Console.WriteLine($"key \"{g.Key}\" -> [{string.Join(", ", g)}]");
Console.WriteLine();
Console.WriteLine($"both keys agree on the grouping: " +
$"{words.GroupBy(SortedKey).Count() == words.GroupBy(CountKey).Count()}");
Console.WriteLine($"SortedKey(\"eat\") = \"{SortedKey("eat")}\"");
Console.WriteLine($"CountKey(\"eat\") = \"{CountKey("eat")}\"");输出：
key "aet" -> [eat, tea, ate]
key "ant" -> [tan, nat]
key "abt" -> [bat]
both keys agree on the grouping: True
SortedKey("eat") = "aet"
CountKey("eat") = "1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0"排序后的字母是最直接的签名，每个单词花 O(m log m)。字母表固定时，统计每个字母出现的次数只要 O(m)，效果一样：输出也证实两种签名得到的分组相同。
有意思的是那些最直接的签名悄悄出错的情况。比如判断“两棵树形状是否相同”，签名必须把空节点也编码进去，否则不同的树会撞到同一个签名上。让签名的强度恰好等于你想要的等价关系，这就是全部工作。
适用场景： 题目说分组、找重复或者有多少个不同的。
模式 28 — 比较器，以及会打乱相等元素顺序的排序
按分数降序排序，分数相同再按名字升序。
(string Name, int Score)[] people =
[
("ada", 90), ("grace", 85), ("alan", 90), ("edsger", 85), ("barbara", 90)
];
// Score descending, then name ascending. One comparer, two keys.
var byScoreThenName = Comparer<(string Name, int Score)>.Create((x, y) =>
{
int c = y.Score.CompareTo(x.Score); // reversed operands = descending
return c != 0 ? c : string.CompareOrdinal(x.Name, y.Name);
});
var arr = people.ToArray();
Array.Sort(arr, byScoreThenName);
foreach (var p in arr) Console.WriteLine($" {p.Name,-8} {p.Score}");
// Array.Sort is NOT stable, and here is exactly where that starts to show.
Console.WriteLine($"\n{"n",4} {"Array.Sort keeps input order?",32}");
foreach (int n in new[] { 8, 16, 17, 32 })
{
var items = Enumerable.Range(0, n).Select(i => (Id: i, Key: i % 2)).ToArray();
var viaSort = items.ToArray();
Array.Sort(viaSort, (x, y) => x.Key.CompareTo(y.Key));
var viaOrderBy = items.OrderBy(p => p.Key).ToArray();
Console.WriteLine($"{n,4} {viaSort.SequenceEqual(viaOrderBy),32}");
}
Console.WriteLine("\n.NET's introsort drops to insertion sort for 16 elements or fewer,");
Console.WriteLine("and insertion sort happens to be stable. At 17 it partitions, and does not.");输出：
ada 90
alan 90
barbara 90
edsger 85
grace 85
n Array.Sort keeps input order?
8 True
16 True
17 False
32 False
.NET's introsort drops to insertion sort for 16 elements or fewer,
and insertion sort happens to be stable. At 17 it partitions, and does not.多键比较器是常规操作：先比第一个键，只有第一个键相等时才比第二个。降序的做法是交换操作数，即 y.CompareTo(x)，而不是对结果取负，因为取负遇到 int.MinValue 会出错。
后半部分才是容易踩坑的地方。
Array.Sort 不稳定，OrderBy 稳定。 再看看它从哪里开始出问题：n = 16 时结果一致，n = 17 时就不一致了。.NET 的内省排序（introsort）在分区不超过 16 个元素时退化为插入排序，而插入排序恰好能保持顺序。超过这个大小就会做划分，相等元素的位置随之改变。
稳定性 bug 在 16 个元素时测试全部通过，到 17 个时才失败。没人会特意挑这个大小来写测试用例。
如果相等元素之间的顺序很重要，要么用 OrderBy/ThenBy，要么给比较器加一个次级键，让任何两个元素都不会相等。竞赛代码用的是后一种，因为对原始数组调用 Array.Sort 更快，而且不分配内存。
适用场景： 按自然顺序以外的任何规则排序。以及任何需要相等元素保持输入顺序的时候。
模式 29 — 坐标压缩（离散化）
值最大到一百万，但不同的值只有寥寥几个。你想要一个按值索引的数组，可它需要一百万个格子。
这些值从头到尾只用来比较大小。所以把值扔掉，只保留它们的排名。
算法一直只用到值的顺序，所以值本身可以扔掉。把不同的值排序，每个值映射到它的位置，问题规模就缩小到不同输入的个数。
int[] a = [1_000_000, 5, 300, 5, 99_999, 300];
// The values matter only by their ORDER, so replace each with its rank.
int[] sorted = a.Distinct().Order().ToArray();
Dictionary<int, int> rank = sorted
.Select((v, i) => (v, i))
.ToDictionary(t => t.v, t => t.i);
int[] compressed = a.Select(v => rank[v]).ToArray();
Console.WriteLine($"original : [{string.Join(", ", a)}]");
Console.WriteLine($"distinct : [{string.Join(", ", sorted)}]");
Console.WriteLine($"compressed : [{string.Join(", ", compressed)}]");
Console.WriteLine();
Console.WriteLine($"an array indexed by value would need {a.Max() + 1:N0} cells");
Console.WriteLine($"an array indexed by rank needs {sorted.Length:N0}");
Console.WriteLine();
// Order is preserved, which is the only property that had to survive.
for (int i = 0; i < a.Length; i++)
for (int j = 0; j < a.Length; j++)
if (a[i].CompareTo(a[j]) != compressed[i].CompareTo(compressed[j]))
throw new Exception("order not preserved");
Console.WriteLine("every pairwise comparison gives the same answer as before: True");
// And it is reversible.
Console.WriteLine($"decompressed: [{string.Join(", ", compressed.Select(r => sorted[r]))}]");输出：
original : [1000000, 5, 300, 5, 99999, 300]
distinct : [5, 300, 99999, 1000000]
compressed : [3, 0, 1, 0, 2, 1]
an array indexed by value would need 1,000,001 cells
an array indexed by rank needs 4
every pairwise comparison gives the same answer as before: True
decompressed: [1000000, 5, 300, 5, 99999, 300]中间那段检查就是全部依据：压缩前后，每一次两两比较的结果都相同。算法依赖的东西一样都没丢。最后一行说明它是可逆的：保留排好序的去重数组，就能把任何排名映射回原值。
代价： 排序 O(n log n)，之后 O(n)。
适用场景： 值很大或者很稀疏，但值的个数很少，比如坐标上的线段树、扫描线、“统计区间内不同值的个数”，以及任何涉及时间戳的问题。
模式 30 — PriorityQueue<TElement, TPriority>
它从 .NET 6 才开始提供。很多 C# 算法竞赛资料比这更早，没有它，只好用 SortedSet 加一个打破平局的键来凑。现在已经不需要这样了。
用它之前，有两点值得先知道。
它是小根堆：优先级最低的先出队。另外，元素和优先级是分开的，正是这一点让第 8 篇里的 Dijkstra 写得清楚：入队时给一个节点配一个距离，而不是把两者塞进一个元组，再写一个比较器。
要保留最大的 k 个值，用大小为 k 的小根堆。这听起来是反的，其实不是：堆顶是当前留下的值里最弱的那个，新来的值正好要胜过它，而且也只值得和它比。
要保留最大的 k 个值，就用小根堆。堆顶是留下的值里最弱的那个，新来的值正好要胜过它，也只有它值得检查。
int[] a = [5, 1, 9, 3, 7, 2, 8];
int k = 3;
// PriorityQueue is a MIN-heap: the smallest priority comes out first.
// To keep the k LARGEST, hold a min-heap of size k and evict its smallest.
PriorityQueue<int, int> topK = new();
foreach (int x in a)
{
if (topK.Count < k)
{
topK.Enqueue(x, x);
Console.WriteLine($"{x} heap not full, keep it -> [{string.Join(",", topK.UnorderedItems.Select(t => t.Element).Order())}]");
}
else if (x > topK.Peek())
{
// One operation instead of Dequeue then Enqueue: one sift, not two.
int evicted = topK.EnqueueDequeue(x, x);
Console.WriteLine($"{x} beats the smallest ({evicted}), swap -> [{string.Join(",", topK.UnorderedItems.Select(t => t.Element).Order())}]");
}
else
{
Console.WriteLine($"{x} loses to the smallest ({topK.Peek()}) -> unchanged");
}
}
List<int> result = [];
while (topK.Count > 0) result.Add(topK.Dequeue());
Console.WriteLine($"\ntop {k} largest, ascending: [{string.Join(", ", result)}]");
// Priority and element are separate, which is what makes Dijkstra readable.
PriorityQueue<string, int> tasks = new();
tasks.Enqueue("write tests", 2);
tasks.Enqueue("fix the bug", 1);
tasks.Enqueue("refactor", 3);
Console.WriteLine();
while (tasks.TryDequeue(out string? task, out int p))
Console.WriteLine($" priority {p}: {task}");输出：
5 heap not full, keep it -> [5]
1 heap not full, keep it -> [1,5]
9 heap not full, keep it -> [1,5,9]
3 beats the smallest (1), swap -> [3,5,9]
7 beats the smallest (3), swap -> [5,7,9]
2 loses to the smallest (5) -> unchanged
8 beats the smallest (5), swap -> [7,8,9]
top 3 largest, ascending: [7, 8, 9]
priority 1: fix the bug
priority 2: write tests
priority 3: refactorEnqueueDequeue 是最值得学走的细节。先入队再出队要调整堆两次；EnqueueDequeue 只调整一次，因为它知道新元素反正马上要和堆顶比较。
它有两样东西没有。一是没有 DecreaseKey，所以 C# 里的 Dijkstra 用的是懒删除：重复入队，出队时跳过过期的项。二是 UnorderedItems 名副其实：它是堆的顺序，不是排好序的顺序。用来查看没问题，用来输出就不行。
代价： 每次入队和出队 O(log n)，空间 O(n)。在 n 个元素上求 top-k 是 O(n log k)。
适用场景： 需要反复取“剩下的最小值”，比如 Dijkstra、k 路归并、任务调度、top-k。
要点
- 先
GetValueOrDefault再赋值，会把键哈希两次。CollectionsMarshal.GetValueRefOrAddDefault只哈希一次，并返回一个ref。 - 小而密集的整数键不需要字典。
int[]更快、更简单，通常也是出题人预期的解法。 - 分组的好坏取决于签名。 签名必须在组内相同、组外不同，不能弱，也不能强。
- 降序是交换操作数，不是对结果取负。 取负遇到
int.MinValue会出错。 Array.Sort超过 16 个元素就不稳定。 恰好 16 个时稳定只是碰巧。用OrderBy，或者加一个次级键，让相等根本不会出现。- 压缩保留顺序，丢掉大小，而这类问题用到的从来只有顺序。保留排好序的去重数组，压缩就是可逆的。
PriorityQueue是小根堆，而求最大的 k 个值正需要小根堆。 用EnqueueDequeue只调整一次而不是两次，另外记住它没有DecreaseKey。
第 7 篇开始讲图，先从图的表示讲起：因为大多数 C# 竞赛题解用的是 List<List<int>>，而它们超时的原因也正在这里。