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

Topic describes

This is the 27. Remove element on LeetCode.

Tag: “Array”, “double pointer”, “array remove element problem”

Given an array of nums and a value of val, you remove all elements with a value equal to val “in place” and return the new length of the removed array.

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

The order of elements can be changed.

You don’t need to worry about the element after the new length in the array.

 

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. Int len = removeElement(nums, val); // 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 = [3,2,2,3], val = 3 Output: 2, nums = [2,2] Explanation: The function should return a new length of 2, and the first two elements of nums are both 2. You don't need to worry about the element after the new length in the array. For example, the function returns a new length of 2, and nums = [2,2,3,3] or nums = [2,2,0,0] will also be considered the correct answer.Copy the code

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3] Explanation: The function should return the new length 5, and the first five elements in nums are 0,1, 3,0,4. Notice that these five elements can be in any order. You don't need to worry about the element after the new length in the array.Copy the code

Tip:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

Double pointer solution

This solution is similar to the “double pointer solution” in [解 析] 26. Delete duplicates in sorted array.

We can divide the array into “before” and “after” segments:

  • The first half is the valid part, the storage is not equal tovalThe element.
  • The second half is the invalid part, and the store is equal tovalThe element.

The final answer returns the end index of the valid part.

Code:

class Solution {
    public int removeElement(int[] nums, int val) {
        int j = nums.length - 1;
        for (int i = 0; i <= j; i++) {
            if(nums[i] == val) { swap(nums, i--, j--); }}return j + 1;
    }
    void swap(int[] nums, int i, int j) {
        inttmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

General solution

This solution is similar to the “general solution” in [解 析] 26. Delete duplicates in sorted arrays.

Set the variable IDx to point to the position to be inserted. The initial value of idX is 0

Then use the “claim/reservation logic” of the problem to decide when to traverse to any elementx, what decisions should be made:

  • If the current elementxAnd removing elementsvalSame, then skip the element.
  • If the current elementxAnd removing elementsvalNo, so let’s put it in the subscriptidxThe location and letidxAutoincrement to the right.

The resulting IDX is the answer.

Code:

class Solution {
    public int removeElement(int[] nums, int val) {
        int idx = 0;
        for (int x : nums) {
            if(x ! = val) nums[idx++] = x; }returnidx; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

conclusion

For things like “Same elements are reserved at mostkIt is better to start from the nature of the topic and extract the specific “reservation logic” based on the given requirements of the topic, and apply the “reservation logic” to every position we traverse.

The last

This is the 27th article in our “Brush through LeetCode” series. The series started on 2021/01/01. There are 1916 questions in LeetCode as of the start date, some of which have lock questions.

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.