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

Question

我在接受采访时被问到这个问题.有一个带有重复项的排序数组.目标是首先返回具有唯一元素的数组,并在最后保留顺序重复.例如[1, 1, 2, 3, 4, 4, 5]应该成为[1, 2, 3, 4, 5, 1, 4].

我能够用额外的空间(O(n)空间)和线性时间(O(n)时间)解决问题,但我不确定这是否是最佳答案,理想情况下不使用线性空间.

我搜索了stackoverflow并发现了类似的问题,但不完全相同.例如,有一个问题排序数组并将重复项移动到最后,但在我的情况下,数组已经排序,目标是仅将重复项移动到最后.

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]