如何高效从海量数据数组获取排序去重数组的元素索引？

原实现中，当数组规模极大、去重排序后的数组也很大时，sortedArray.IndexOf(x)会导致严重的性能问题——因为IndexOf是线性查找，每次调用都要遍历整个去重数组，时间复杂度达到O(N*M)（N为原数组长度，M为去重后数组长度），数据量越大越慢。

优化方案：用字典建立元素到索引的映射 #

通过Dictionary构建元素与对应索引的键值对，利用字典近似O(1)的查找性能，将整体时间复杂度降至O(N + M log M)（主要耗时在排序步骤）。

优化后的代码示例：

var array = new[] {3, 7, 8, 3, 9, 9};
// 去重排序后，直接构建元素到索引的字典映射
var valueIndexMap = array.Distinct()
                         .OrderBy(x => x)
                         .Select((val, idx) => new { val, idx })
                         .ToDictionary(item => item.val, item => item.idx);
// 遍历原数组，通过字典快速获取索引
var result = array.Select(x => valueIndexMap[x]).ToArray();

性能说明 #

1. 字典构建阶段：去重排序后，通过Select带索引的重载直接绑定元素与索引，再转成字典，耗时O(M)
2. 结果生成阶段：遍历原数组时，每次查找字典都是近似O(1)操作，总耗时O(N)
3. 相比原方案，当M达到万级以上时，性能提升会非常显著

注意事项 #

• 如果数组元素是引用类型且可能为null，需要确保字典允许null作为键（默认Dictionary支持引用类型的null键）
• 原数组中的重复元素，字典已经通过Distinct()去重，直接查找即可得到正确的索引

内容的提问来源于stack exchange，提问作者user3819226