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

Question

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

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

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

标签： arraysalgorithmsorting

Answer 1

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

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

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

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

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]