寻找平均时间复杂度O(n)的特殊部分有序数组排序算法

算法思路 #

题目给出的数组有一个核心特性：值越小的元素，首次出现的位置越早（任意x<y时，x的首次出现早于y的首次出现）。这意味着数组中元素的首次出现顺序恰好是升序排列，因此我们不需要对元素值做额外排序，只需要统计每个元素的出现次数，再按首次出现的顺序展开即可得到有序数组。

具体步骤 #

1. 统计次数+记录首次出现顺序
   • 用哈希字典count_map存储元素与出现次数的映射，用列表order_list记录元素首次出现的先后顺序。
   • 遍历输入数组：
     • 若元素不在count_map中，将其加入order_list，并在count_map中初始化计数为1。
     • 若元素已在count_map中，将对应计数加1。
2. 生成结果数组
   • 初始化空结果数组result。
   • 遍历order_list中的每个元素，将该元素重复count_map中对应的次数，依次追加到result中。

代码示例（Python） #

def sort_special_array(arr):
    count_map = {}
    order_list = []
    for num in arr:
        if num not in count_map:
            order_list.append(num)
            count_map[num] = 1
        else:
            count_map[num] += 1
    # 构建结果
    result = []
    for num in order_list:
        result.extend([num] * count_map[num])
    return result

# 测试示例输入
input_arr = [1,2,1,30,1,1,2,1,40,30,1,40,2,50,40,50,30]
print(sort_special_array(input_arr))
# 输出: [1,1,1,1,1,1,2,2,2,30,30,30,40,40,40,50,50]

平均时间复杂度证明 #

我们分两个阶段拆解时间复杂度：

1. 统计阶段：遍历数组的n个元素，每个元素的哈希表查找/插入操作平均时间为O(1)（哈希表的平均访问、插入操作均为常数时间），因此该阶段总时间为O(n)。
2. 结果构建阶段：遍历order_list中的唯一元素，每个元素的展开次数等于其出现次数，所有元素的出现次数总和为n，因此该阶段总时间也为O(n)。

将两个阶段的时间相加，总时间为O(n) + O(n) = O(n)，且该平均时间复杂度成立（哈希表平均访问特性保证了统计阶段的线性时间）。

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