Aunt Guan is participating in the “Java Theme month – Java brush question clocking”, see the activity link for more details

First of all, I would like to clarify that every algorithm problem has multiple solutions. We will only talk about several excellent solutions in LeetCode, hoping to help you. Let’s first look at the description of the problem

I. Title Description:

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

Instead of using extra array space, you must only use 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.

Example 1:

Given nums = [3,2,2,3], val = 3,

The function should return a new length of 2, and the first two elements in nums are both 2.

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

Example 2:

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

The function should return a new length of 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.

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

Ii. Analysis of Ideas:

1. Double pointer

If you understood the last problem a little bit better, you can easily see that this one can also be done with double Pointers. How do you do that? We also keep two Pointers I and j, where I is the slow pointer and j is the fast pointer, both traversing from 0. If nums[j] is equal to the given value, it indicates that it is the element we want to remove, and then increments j to determine whether the next number is equal to the given value. If nums[j] is still equal to the given value, then nums[j] is assigned to nums[I], and then I and j increments I and j at the same time. Repeat the process until j reaches the end of the array with length I.

Code demo

public int removeElement(int[] nums, int val) { int i = 0; Int j=0 for (int j=0; j < nums.length; If (nums[j]! = val) {if (nums[j]! = val) { = val) { nums[i] = nums[j]; i++; }} // returns I, not I +1, why? Because j starts at 0, not at I +1, you can think about return I; }Copy the code

Complexity analysis

Time complexity: O(n) Assuming a total of n elements in the array, I and j traverse at least 2n steps. Space complexity: O(1).

2. Advanced version of dual pointer

Now consider a special case where the array contains very few elements to delete. For example, the algorithm before num=[1,2,3,5,4] and Val=4 would make unnecessary copies of the first four elements. Another example is num=[4, 1,2,3,5] and Val=4. It seems unnecessary to move the elements [1,2,3,5] one step to the left because the order of the elements mentioned in the problem description can be changed. So what to do? When nums[I] = val, we swap the current element with the last element in the array. This ensures that all elements equal to the given value are moved to the very end of the array. In this way, we reduce the length of the array by abandoning the element with val.

Code demo

public int removeElement(int[] nums, int val) { int i = 0; int n = nums.length; While (I < n) {if (nums[I] == val) {nums[I] = nums[n-1]; // Notice that the last element may also be val, so we don't increment I with n--; } else {// If the current element is not the one we are looking for, then I increments, traversing the next I ++; } } return n; }Copy the code

Complexity analysis

Time complexity: O(n), I and n traversal at most N steps. In this method, the number of assignment operations is equal to the number of elements to delete. Therefore, it is more efficient if there are few elements to remove. Space complexity: O(1)

Brush question summary

If you have other ideas to solve the problem, as long as you can achieve the requirements, it is no problem, all roads lead to Rome, not just limited to the solution I said ha ~, excellent ideas and code is more learning significance, let’s work together