将重复项移动到已排序数组的末尾 [英] Move duplicates to the end of a sorted array

问题描述

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

I was asked this question in an interview. There is a sorted array with duplicates. The goal is to return the array with unique elements first and duplicates at the end preserving the order. For example [1, 1, 2, 3, 4, 4, 5] should become [1, 2, 3, 4, 5, 1, 4].

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

I was able to solve the question with an extra space (O(n) space) and linear time (O(n) time), but I am not sure if that is the best answer, ideally using no linear space.

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

I searched stackoverflow and found similar questions but not exactly the same. For example there was a question sorting an array and moving duplicates to the end, but in my case the array is already sorted and the goal is to only move duplicates to the end.

推荐答案

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

If your values are in limited range, there exists solution in O(n) time and O(1) space.

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

Determine the maximum value in array. Get some constant C > arraymax, as example - C = 10 for your array.

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

Scan array, squeezing unique values and counting duplicates for every value. If value V has K>0 duplicates, write V+C*K instead of value.

在下一次扫描中找到重复的值，提取重复的数量并在挤压唯一值后写入.

At the next scan find values with duplicates, extract number of duplicates and write them after squeezed unique values.

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]

这篇关于将重复项移动到已排序数组的末尾的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！