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删除有序数组中重复的元素；返回新的长度；不允许新建额外的数组
解决思路
- 设立2个游标：游标index用来遍历数组，游标newLen用来插入元素
- 遍历数组，两两比较；如果不同，将index指向的元素复制到newLen指向位置；newLen与index各自右移
package com.rust.cal;
public class RemoveDuplicatesfromSortedArray {
public static int removeDuplicates(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
int index = 1;
int newLen = 1; // return value
while(index < nums.length){
if (nums[index] != nums[index - 1]) {
nums[newLen] = nums[index]; // insert element
newLen++;
}
index++;
}
return newLen;
}
public static void main(String args[]){
int[] input = {1,2,2,3,4,5,5,5,5,5,6,6,6,7,7,7,7,8};
System.out.println("new lengh: " + removeDuplicates(input));
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + " ");
}
}
}输出：
new lengh: 8
1 2 3 4 5 6 7 8 5 5 6 6 6 7 7 7 7 8 
