首页 > 代码库 > LeetCode--Remove Duplicates from Sorted Array

LeetCode--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 A = [1,1,2],

Your function should return length = 2, and A is now [1,2]

问题:

  把给定数组中重复的值去掉,并且返回去重后数组长度,注意题目要求不能再定义另一个数组,所以结果还保存在输入数组内。

思路:

  从前到后两两进行比较,如果不等,就存入A中,相等的话就后移直到每次找到不等的值保存结果,最后用新的结果数组的索引记录长度。

  例如数组[1,2,2,3,4,5,5,6]

  首先比较定义result=1,A[result++]用来保存结果数组。

  1!=2  所以 A[result]为A[1],所以A[1]=2,另result++后result==2;

  2==2 所以 不保存,继续向后循环比较。

  2!=3  所以 A[result]为A[2],所以A[2]=3,另result++后result==3‘

  .......

  循环直到结束,result为新数组长度,A为去重后数组

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

 

LeetCode--Remove Duplicates from Sorted Array