LeetCode - Easy - 26. Remove Duplicates from Sorted Array

﹏ヽ暗。殇╰゛Y 2022-12-27 06:24 62阅读 0赞

## Topic ##

Array, Two Pointers

## Description ##

[https://leetcode.com/problems/remove-duplicates-from-sorted-array/][https_leetcode.com_problems_remove-duplicates-from-sorted-array]

Given a **sorted** array nums, remove the duplicates **in-place** such that each element appears only once and returns the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

--------------------

**Clarification**:（讲述调用函数，参数传值而非传引用，可忽略）

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by **reference**, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
    int len = removeDuplicates(nums);
    
    // any modification to nums in your function would be known by the caller.
    // using the length returned by your function, it prints the first len elements.
    for (int i = 0; i < len; i++) { 
        print(nums[i]);
    }

--------------------

**Example 1**:

Input: nums = [1,1,2]
    Output: 2, nums = [1,2]
    Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

**Example 2**:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
    Output: 5, nums = [0,1,2,3,4]
    Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

--------------------

**Constraints**:

*  0 <= nums.length <= 3 \* 10⁴
 *  \-10⁴ <= nums\[i\] <= 10⁴
 *  nums is sorted in ascending order.

## Analysis ##

用两指针法，并利用数组有序的属性进行解答，注意两指针下标的协调。

## Submission ##

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

## Test ##

import static org.junit.Assert.*;
    
    import java.util.Arrays;
    
    import org.junit.Test;
    
    public class RemoveDuplicatesFromSortedArrayTest { 
    
    	@Test
    	public void test() { 
    		RemoveDuplicatesFromSortedArray obj = new RemoveDuplicatesFromSortedArray();
    
    		int[] array = { 0,0,1,1,1,2,2,3,3,4};
    		int expectNum = 5;
    		assertEquals(expectNum, obj.removeDuplicates(array));
    		assertArrayEquals(new int[] { 0,1,2,3,4}, Arrays.copyOfRange(array, 0, expectNum));
    	}
    }

[https_leetcode.com_problems_remove-duplicates-from-sorted-array]: https://leetcode.com/problems/remove-duplicates-from-sorted-array/