This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 80 on LeetCode. Removing duplicates II from an ordered array is of moderate difficulty.

Tag: double pointer

Given an ordered array of nums, you are asked to “in place” remove the repeated elements, so that each element appears at most twice, returning the new length of the deleted array.

Instead of using extra array space, you must modify the input array “in place” and do so with O(1)O(1)O(1) extra space.

 

Description:

Why is the return value an integer, but the output answer is an array?

Note that the input array is passed “by reference,” which means that modifying the input array in a function is visible to the caller.

You can imagine the internal operation as follows:

// Nums is passed by reference. That is, it does not make any copies of the arguments int len = removeDuplicates(nums); // Modifying the input array in a function is visible to the caller. // Depending on the length returned by your function, it prints out all elements in the array within that length. for (int i = 0; i < len; i++) { print(nums[i]); }Copy the code

Example 1:

Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3] Explanation: The function should return the new length = 5, and the first five elements of the original array are modified to 1,1,2,2,3. You don't need to worry about the element after the new length in the array.Copy the code

Example 2:

Input: nums =,0,1,1,1,1,2,3,3 [0] output: 7, nums =,0,1,1,2,3,3 [0] interpretation: The function should return the new length = 7, and the first five elements of the original array are modified to 0, 0, 1, 1, 2, 3, 3. You don't need to worry about the element after the new length in the array.Copy the code

Tip:

  • 1 <= nums.length <= 3 *
    1 0 4 10^4
  • –
    1 0 4 10^4     <= nums[i] <=
    1 0 4 10^4
  • Nums are sorted in ascending order

General solution

In order to make the solution more general, we changed the original “reserved 2 bits” to “reserved K bits”.

For such questions, we should consider the following:

  • Because it’s a reservationkThe same number,For the formerkA number. We can just keep it
  • Any subsequent number can be retained only if it is compared with the KTH element before the current position

For example 🌰, let’s set k=2. Suppose we have the following example

,1,1,1,1,1,2,2,2,2,2,2,3 [1]

  1. So let’s just keep the first two bits, so we get 1,1
  2. Continue traversing each of the following bits, preserving the premise that precedes the current positionkThe elements are different (the first 1 in the answer), so we skip the remaining 1 and append the first 2 to get 1,2
  3. So if I keep going, I’m going to compare it to the second 1 in the answer, so I get 1,1,2,2
  4. Only elements different from the first 2 can be appended to the answer, so the remaining 2 is skipped and 3 is appended to the answer: 1,1,2,2,3

Code:

class Solution {
    public int removeDuplicates(int[] nums) {   
        return process(nums, 2);
    }
    int process(int[] nums, int k) {
        int u = 0; 
        for (int x : nums) {
            if(u < k || nums[u - k] ! = x) nums[u++] = x; }returnu; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

other

This is a kind of “data ordered, the same elements remainkBit “problem more essential solution, the solution is extracted from the properties, using the” array order & retention logic “two major properties.

Once you have mastered this general solution, you can remove duplicates from an ordered array by changing the code above by one digit.

This general solution was first described in the “two-pointer” and “general” solutions.

The last

This is the No.80 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.