python - 如何改进删除重复算法？

Question

我的面试问题是我需要返回删除重复项的数组的长度，但我们最多可以保留 2 个重复项。

例如，[1, 1, 1, 2, 2, 3] 新数组将是 [1, 1, 2, 2, 3]。所以新的长度将是 5。我想出了一个 O(2n) 我相信的算法。我怎样才能提高它是最快的。

def removeDuplicates(nums):
    if nums is None:
        return 0

    if len(nums) == 0:
        return 0

    if len(nums) == 1:
        return 1

    new_array = {}
    for num in nums:
        new_array[num] = new_array.get(num, 0) + 1

    new_length = 0
    for key in new_array:
        if new_array[key] > 2:
            new_length = new_length + 2
        else:
            new_length = new_length + new_array[key]

    return new_length

new_length = removeDuplicates([1, 1, 1, 2, 2, 3])
assert new_length == 5

我的第一个问题是我的算法是否正确？

Answer 1

您的逻辑是正确的，但他是实现您在问题中提到的目标的更简单方法。

这是我的逻辑。

myl = [1, 1, 1, 2, 2, 3, 1, 1, 1, 2, 2, 3, 1, 1, 1, 2, 2, 3]

newl = []

for i in myl:
    if newl.count(i) != 2:
        newl.append(i)

print newl
[1, 1, 2, 2, 3, 3]

希望这对您有所帮助。