如何高效实现列表的原地重编号（忽略0值）？

问题回顾 #

输入数组包含非零元素和需忽略的0，需在保持原位置不变的前提下，将非零元素按从小到大排序后的出现顺序重编号（示例：{5,0,23,2,2,0} → {3,0,4,1,2,0}）。原方案通过排序数组副本+双重循环匹配，时间复杂度达O(n²)，性能瓶颈明显。

优化方案1：带原始索引的排序映射 #

此方案将时间复杂度降至O(m log m + n)（m为非零元素数量），适用于元素值范围较大的场景：

1. 构建带索引的元素集合
   定义结构体存储非零元素的值和原始索引：

   typedef struct {
       int val;
       int idx;
   } Element;
   

   遍历原数组，将所有非零元素的<值, 原始索引>对存入该结构体数组。

2. 排序结构体数组
   编写qsort的比较函数，优先按元素值从小到大排序，值相同时按原始索引排序（保证同值元素的编号顺序与原数组一致）：

   int compare(const void *a, const void *b) {
       Element *elemA = (Element *)a;
       Element *elemB = (Element *)b;
       if (elemA->val != elemB->val) {
           return elemA->val - elemB->val;
       } else {
           return elemA->idx - elemB->idx;
       }
   }
   

   调用qsort对结构体数组排序。

3. 生成结果数组
   初始化结果数组为0，遍历排序后的结构体数组，将第i个元素（从0开始）的编号i+1填入结果数组对应原始索引的位置。

优化方案2：基于计数的分组映射 #

此方案时间复杂度为O(n + K)（K为非零元素的最大值），适用于元素值范围较小的场景：

1. 分组存储元素索引
   找到非零元素的最大值max_val，创建动态数组/链表数组list，其中list[x]存储所有值为x的元素的原始索引。
   遍历原数组，将每个非零元素的索引添加到对应list[x]中。

2. 分配编号并填充结果
   初始化结果数组为0，设置编号计数器count=1。
   从x=1到x=max_val遍历：

   • 若list[x]不为空，依次遍历其中的索引，将count赋值给结果数组对应位置，每赋值一次count++。

方案对比 #

• 当元素值范围大（如1e9级别），优先选择带索引的排序映射，避免内存浪费。
• 当元素值范围小（如1e4级别），计数分组映射的性能更优，无需排序操作。

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