How to improve duplicate removal algorithm?

Question

My question was that I need to return the length of the array that deleted the duplicates, but we can leave no more than two duplicates.

For example, [1, 1, 1, 2, 2, 3] new array will be [1, 1, 2, 2, 3] . So the new length will be equal to 5. I came up with an algorithm with O (2n), I believe. How can I improve this 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 will be my algorithm, even the right one?

Answer 1

Your logic is correct, but it is an easier way to achieve the goal that you spoke about in your question.

Here is my logic.

 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] 

Hope this helps.

Answer 2

If the initial size of the array is n .

• Count the various numbers in your array.

• If you have d different numbers then your answer will be

    d (when n == d) d+1 (when n == d+1) d+2 (when n >= d+2) 

If all the numbers in your array are less than n-1 , you can even solve this without using extra space. If this case checks this , and you can easily count different numbers without extra space.

Answer 3

I would forget about creating a 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 

Answer 4

 int removeDuplicates(vector<int>& nums) { if (nums.size() == 0) return nums.size(); int state = 1; int idx = 1; for (int i = 1; i < nums.size(); ++i) { if (nums[i] != nums[i-1]) { state = 1; nums[idx++] = nums[i]; } else if (state == 1) { state++; nums[idx++] = nums[i]; } else { state++; } } return idx; } 

idea: save a variable (state) that fixes the current repetition times (more precisely, the state records the repeating moments of an element that are adjacent to the left of the current element). This algorithm is O (n) with one array scan.

Answer 5

 def removeDuplicates(nums): if nums is None: return 0 if len(nums) == 0: return 0 if len(nums) == 1: return 1 new_array_a = set() new_array_b = set() while nums: i = nums.pop() if i not in new_array_a: new_array_a.add(i) elif i not in new_array_b: new_array_b.add(i) return len(new_array_a) + len(new_array_b)