This is the 19th day of my participation in the August Wen Challenge.More challenges in August

Remove duplicates from an ordered array

Topic describes

Give you an ordered array nums, ask you to delete the repeated elements in place, so that each element appears only once, return the deleted array after the new length.

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

instructions

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

The sample

  • Example 1:

Input: nums = [1,1,2]

Output: 2, nums = [1,2]

Explanation: The function should return a new length of 2, and the first two elements of the original nums array should be changed to 1, 2. You don’t need to worry about the element after the new length in the array.

  • Example 2:

Input: nums = [0,0,1,1, 2,2,3,3,4]

5, nums = [0,1,2,3,4]

Explanation: The function should return a new length of 5, and the first five elements of the original nums array are changed to 0, 1, 2, 3, 4. You don’t need to worry about the element after the new length in the array.

prompt

  • 0 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • Nums are sorted in ascending order

Thought analysis

This problem is to use two hands, one is the function of the cursor, in charge of traverse the entire array, a is a function of positioner, if there are equal locator has said, pointing to the element is repetitive, locator motionless, waiting for the cursor down to find not to repeat the number of fill in, as the cursor traverses the entire array and always faster than locator, So one element in the array is no longer used after the cursor traverses it, and the number that does not repeat is simply inserted into the locator position, which is moved back synchronously, and the locator position +1 is the length of the array.

Code implementation

class Solution { public int removeDuplicates(int[] nums) { int index = 0; if(nums.length == 0){ return index; } else { for(int i = 0; i < nums.length; i++){ if(nums[i] ! = nums[index]){ nums[++index] = nums[i]; } } return index+1; }}}Copy the code

Write in the last

26. Delete duplicates in ordered arrays – LeetCode (leetcode-cn.com)

Welcome to put forward new ideas!