如何提高删除重复的算法？

本文介绍了如何提高删除重复的算法？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我的面试问题是，我需要返回一个数组，删除重复的长度，但我们可以把最多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