Removes duplicates from the sorted array

  • 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.

 

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,2] Output: 2, nums = [1,2] Explanation: The function should return a new length of 2, and the first two elements of the original array nums are changed to 1,2. You don't need to worry about the element after the new length in the array.Copy the code

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2, 2,3,4] Explanation: The function should return a new length of 5, and the first five elements of the original array NUMs are modified to 0,1,2,3,4. You don't need to worry about the element after the new length in the array.Copy the code
0 <= nums.length <= 3 * 104-104 <= nums[I] <= 104 NUMs are sorted in ascending orderCopy the code

My answer:

/** * @param {number[]} nums * @return {number} */ var removeDuplicates = function(nums) { if (nums.length == 0) return 0; let i = 0; for (let j = 1; j < nums.length; j++) { if (nums[j] ! = nums[i]) { i++; nums[i] = nums[j]; } } return i + 1; };Copy the code

Answers and analysis from others:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int slow = 0, fast = 1;
        while (fast < nums.size()) {
            if (nums[slow] != nums[fast])
                 nums[++slow] = nums[fast];
            fast++;
        }

        return slow+1;
    }
};
Copy the code

First of all, this question is clear, the key is to clarify the meaning of the fast pointer: the fast pointer is to detect the current element, while the slow pointer is already determined, and the previous element without repetition of the pointer.

So, in fact, the element pointed to by fast is the one we want to detect, while the slow pointer is already identified and has no duplicate elements.

After describing the meaning of fast and slow Pointers, this topic can be written. At the same time, the most important point, when slow and FAST initialization, it is very necessary to clarify the meaning, which is conducive to write concise and easy to understand the code.

At the same time, according to the definition of the slow pointer, we can actually see that when nums is empty, there is no way to wrap the situation in, because slow is the identified element, provided there is an element, so a separate if column is required.

Ensuring clear thinking is the key to solving more difficult problems. Clear definitions ensure that initialization and variable handling are accurate, and that adequate and correct code is written.