如何提高删除重复的算法？ [英] How do I improve remove duplicate algorithm?

问题描述

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

My interview question was that I need to return the length of an array that removed duplicates but we can leave at most 2 duplicates.

例如， [1，1，1，2，2，3] 新阵列将 [1，1，2， 2，3] 。因此，新的长度是5，我想出了一个算法O（2n）的，我相信。我怎样才能改善这种是最快的。

For example, [1, 1, 1, 2, 2, 3] the new array would be [1, 1, 2, 2, 3]. So the new length would be 5. I came up with an algorithm with O(2n) I believe. How can I improve that to be the fastest.

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

我的第一个问题将是我的算法，即使是正确的？

My first question would be is my algorithm even correct?

推荐答案

我忘了生成新的阵列和只专注于计数：

I'd forget about generating the new array and just focus on counting:

from collections import Counter

def count_non_2dups(nums):
    new_len = 0
    for num, count in Counter(nums).items():
        new_len += min(2, count)
    return new_len

这篇关于如何提高删除重复的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！