将重复项移动到已排序数组的末尾

我在一次采访中被问到这个问题。 有一个包含重复项的已排序数组。 目标是首先返回具有唯一元素的数组，并在最后返回重复的元素并保持顺序。 例如[1, 1, 2, 3, 4, 4, 5]应该成为[1, 2, 3, 4, 5, 1, 4].

我能够用额外的空间（O(n) 空间）和线性时间（O(n) 时间）来解决这个问题，但我不确定这是否是最好的答案，最好不使用线性空间。

我搜索了stackoverflow，发现了类似的问题，但不完全相同。例如有一个question https://stackoverflow.com/questions/7238023/sorting-an-array-while-moving-duplicates-to-the-end对数组进行排序并将重复项移动到末尾，但在我的情况下，数组已经排序，目标是仅将重复项移到末尾。

如果您的值在有限范围内，则存在 O(n) 时间和 O(1) 空间的解决方案。

确定数组中的最大值。得到一些常数C > arraymax，例如 -C = 10为你的数组。

扫描数组，压缩唯一值并计算每个值的重复项。如果值V has K>0重复，写V+C*K而不是价值。

在下一次扫描时查找具有重复项的值，提取重复项的数量并将其写入压缩后的唯一值之后。

def dedup(lst):
    mx = max(lst) + 1
    dupcnt = 0
    delcnt = 0
    start = 0
    for i in range(1, len(lst) + 1):
        if i == len(lst) or (lst[i] != lst[start]):
            lst[start - delcnt] = lst[start] + dupcnt * mx
            delcnt += dupcnt
            start = i
            dupcnt = 0
        else:
            dupcnt += 1
    dupidx = len(lst) - delcnt
    for i in range(0, len(lst) - delcnt):
        dupcnt = lst[i] // mx
        if dupcnt:
           lst[i] %= mx
           for j in range(dupidx, dupidx+dupcnt):
              lst[j] = lst[i]
           dupidx += dupcnt
    return lst

print(dedup([1,2,2,2,3,4,4,5]))
>>> [1, 2, 3, 4, 5, 2, 2, 4]