Leetcode-26-Remove Duplicates from Sorted Array

 

Remove Duplicates from Sorted Array

 

 

 

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

 

Do not allocate extra space for another array, you must do this in place with constant memory.

 

For example,

 

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

 

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 new length.

 

题目解读：

 

给定一个有序数组，删除数组中重复的元素，使数组中的每个元素只出现一次，返回新数组的长度。不允许申请额外数组空间，必须在常量个内存空间中完成。例如给定一个数组nums=[1,1,2]。函数的返回结果为length=2，并且剩余数组中的前两个元素必须是1和2。剩余数组的长度大小无所谓。

 

解析：

 

由于数组是有序的，所以重复的数组元素是紧挨着的两个或多个。则在算法中需要使用当前元素与下一元素进行比较，如果下一元素与当前元素相同，则删除下一元素，以此类推。如下图所示：

 Java代码：

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

 

程序性能：