编程知识 cdmana.com

Delete duplicate items in sorted array (Java implementation)

Title Description

Given a sort array , You need to In situ Delete duplicate elements , So that each element only appears once , Returns the new length of the array after removal .

Don't use extra array space , You must be there. In situ Modify input array And using O(1) Complete with extra space .

 

Example  1:

Given array nums = [1,1,2], 

Function should return the new length 2, And the original array nums The first two elements of are modified to 1, 2. 

You don't need to think about the elements in the array that follow the new length .
Example  2:

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

Function should return the new length 5, And the original array nums The first five elements of are modified to 0, 1, 2, 3, 4.

You don't need to think about the elements in the array that follow the new length .
 

explain :

Why is the return value an integer , But the output answer is array ?

Please note that , The input array is based on 「 quote 」 By way of transmission , This means that modifying the input array in a function is visible to the caller .

You can imagine the internal operation as follows :

// nums In order to “ quote ” By way of transmission . in other words , Do not make any copies of the arguments
int len = removeDuplicates(nums);

// Modifying the input array in a function is visible to the caller .
// Based on the length returned by your function , It prints out all elements of the array in that length range .
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

source : Power button (LeetCode) link :https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

Their thinking

Method : Double finger needling
Algorithm

After sorting the array , We can put two pointers i and j, among i It's a slow pointer , and j  It's a quick pointer . as long as nums[i] = nums[j], We will increase j  To skip duplicates .

When we meet nums[j] It's not equal to nums[i] when , Skipping duplicates is over , So we have to put it (nums[j]) Copy the value of to nums[i + 1]. Then increments i, Then we will repeat the same process again , until j  Until the end of the array .

( Source of ideas : Power button (LeetCode) link :https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-xiang-by-/)

Solution code

Complexity analysis

  • Time complexity :O(n), Let's say the length of the array is  n, that  i  and  j  Most of them are traversal  n  Step .

  • Spatial complexity :O(1).

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

 

版权声明
本文为[Cheng Yu]所创,转载请带上原文链接,感谢

Scroll to Top