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

Question

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

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

我搜索了stackoverflow，发现了类似但不完全相同的问题。例如有一个 question对数组进行排序并将重复项移动到末尾，但在我的例子中，数组已经排序，目标是只将重复项移动到末尾。

Answer 1

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

确定数组中的最大值。获取一些常量 C > arraymax，例如 - C = 10 用于您的数组。

扫描数组，压缩唯一值并计算每个值的重复项。如果值 V 有 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]