This article originated from personal public account: TechFlow, original is not easy, for attention


First, Remove Duplicates from Sorted Array II. First, delete the Sorted Array.

The official difficulty of this question is Medium, with a 43.3% pass rate of 1,104 upvotes and 690 downvotes. This one has a slightly higher pass rate, and not a very high like rate. It shows that this question is easy and underrated. And indeed, I personally think that the main reason people don’t like it is that it’s a little bit easier.

theme

In fact, from the title of the title we can already get a lot of information, in fact, it is true, the topic and the title of the problem is almost inseparable, we needDeduplicates an ordered array. However, the condition is to allow a maximum of two occurrences of an element, that is, to remove the redundant elements. And they also limit the amount of space that we need to operate on the original array. Since removing the elements will change the length of the array, we finally need to return the length of the array after completion.

This is a general practice, in C++ and some older languages you cannot change the length of arrays. If we want to delete data from the original array, we can only move the deleted data to the end of the array and return the changed array length. The downstream will then know the change in quantity from the returned array length. Since newer languages such as Java and Python support variable array lengths, it is rare to see such usage in their code.

The sample

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length. Copy the code

In this example, since 1 occurs four times, we need to remove two 1’s, which will reduce the array length by two, so we need to return 7 to indicate that the effective length of the new array after deletion is 7. And make sure the first five elements of the array are [0, 0, 1, 1, 2, 3].

Answer key

Removing duplicate elements is not complicated in itself, the only problem is how to do it without introducing additional storage. If you can grasp the fact that arrays are ordered, it should be easy to figure out that since arrays are ordered, the same elements must be placed next to each other.

Since the same elements are grouped together, we can use a variable to store the number of occurrences of the current element. If different elements are encountered, set the degree to 1. This allows us to determine which elements need to be removed and which elements need to be kept.

But that brings up another problem, how do we remove these duplicate elements? Because we can’t introduce additional arrays, we need to do it on the current array. So let’s assume that we don’t have this constraint, what do we do?

new_nums = []
cur = None
for i in range(n):
    if cur == nums[i]:
        count += 1
 else:  count = 1  cur = nums[i]  if count > 2:  continue  new_nums.append(nums[i]) Copy the code

Because of this limitation, all we need to do is remove the new_nums array, which is easy because we can make nums overwrite itself. Because the amount of output data must be less than or equal to the length of the array, there is no problem with the array being out of bounds. All we need to do is maintain a subscript record of the positions in the NUMS array that are allowed to be overridden.

This is also a very common practice, and we saw it in the previous problem.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # start is the initial overwrite pointer, pointing to the first position that can be overwritten
        start, cur, cnt = 0.None.0
        n = len(nums)
 if n == 0:  return 0  for i in range(n):  if cur == nums[i]:  cnt += 1  else:  cnt = 1  cur = nums[i]  Continue if the number exceeds 2, indicating that the current element should be discarded  if cnt > 2:  continue  Otherwise overwrite the start position with the current element, and start moves one bit  else:  nums[start] = nums[i]  start += 1  return start Copy the code

There is a simplified version of this code where we can omit the CNT variable as well. Nums [I] = nums[i-2] = nums[i-2] = nums[I] = nums[i-2]

The simplified code looks like this:

class Solution(object):
    def removeDuplicates(self, nums):
        "" "        :type nums: List[int]
 :rtype: int "" "  i = 0  for n in nums:  if i < 2 orn ! = nums[i -2] : nums[i] = n  i += 1  return i Copy the code

conclusion

Today’s topic is not difficult. Generally speaking, it is considered as a Medium difficulty. There are two main points worth praising. The first is the C++ style way inplace changes arrays, and the second is the way arrays cover themselves. Other than that, the problem is hardly difficult, and I think you should be able to figure it out.

If you like this article, if you can, please click the following, give me a little encouragement, but also convenient access to more articles.

This article is formatted using MDNICE