This is the 24th day of my participation in Gwen Challenge

preface

The removed elements in question 27 are as follows:

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:

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.

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.

A, thinking

In fact, this problem is a bit similar to the twenty-sixth problem – delete the ordered array of duplicate items, are in place to modify the array, and return the length of the array after processing, can ignore the array beyond the length of the elements.

The idea is to iterate through the array, aggregating all elements that are not equal to each other to the left of the array. Since the elements that exceed the length do not need to be processed, you do not need to actually remove the elements that are equal.

The specific steps are as follows:

  1. Records the index of the new arraycurrent, current The default value is 0. The results ofret = 0
  2. The current element and the target element are iterated from the second element of the nums array
    • If equal: no processing is done.
    • If not equal: if previous elements have been deleted, i.ei ! = currentThat will benums[current] = nums[i]. thencurrent++.ret++
  3. returnretCan be

Practical example analysis

Nums = [3,2, 3] and val = 3 in Example 1 are used as examples.

  1. The initial valuecurrent = 0.ret = 0
  2. I start walking,nums[0] == val (3 == 3), so no processing
  3. nums[1] ! = val (2 ! = 3) 且 i ! = current (1 ! = 0)That will benums[0] = 2. thencurrent = 1, ret = 1
  4. nums[2] ! = val (2 ! = 3) 且 i ! = current (2 ! = 1)That will benums[1] = 2. thencurrent = 2, ret = 2
  5. I start walking,nums[3] == val (3 == 3), so no processing
  6. Returns the resultret = 2In fact, this arraynums = [2, 2, 2, 3], but there is no influence because the element with excess length can be ignored.)

Second, the implementation

The implementation code

    public int removeElement(int[] nums, int val) {
        int ret = 0;
        int current = 0;    // The current position
        for (int i=0; i<nums.length; i++) {
            if(val ! = nums[i]) {if(i ! = current) {// There was an element deletednums[current] = nums[i]; } ret++; current++; }}return ret;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int[] nums = {0.0.1.1.1.2.2.3.3.4};
        new Number26().removeDuplicates(nums);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥