【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].

这个题目挺简单的，就是删除数组中的重复元素就行，而且数组还已经排好序了。

接下来我们要做的就是考虑细节问题了，我的做法是首先考虑特殊输入（也可以说是非法输入什么的），比如：输入如果是0、1怎么办，然后考虑复杂度一定很容易能想到O(n)的算法（千万不要O(n^2)），想到这些题目就很简单了。

我的做法是这样的：用一个值记录前面有几个重复的了，后面的直接转移到它应在的位置，一步到位。

代码如下：

 1 class Solution {
 2 public:
 3     int removeDuplicates(int A[], int n) {
 4         if(n==0)
 5         {
 6             return 0;
 7         }
 8         if(n==1)
 9         {
10             return 1;
11         }
12         int pre=A[0];
13         int flg=0;
14         for(int i=1;i<n;i++)
15         {
16             if(pre==A[i])
17             {
18                 pre=A[i];
19                 flg++;
20             }
21             else
22             {
23                 pre=A[i];
24                 A[i-(flg)]=A[i];
25             }
26         }
27         return n-flg;
28     }
29 };

虽然题目很简单，但是还是有些值得我们学习得，通过leetcode的练习我觉得收获得不仅仅是算法方面的知识，更多的应该是考虑问题的全面性，直接一点就是每一道题都可以假设是你在面试中遇到，在实现之前你要怎么考虑。keep going！

【leetcode】Remove Duplicates from Sorted Array,布布扣,bubuko.com

【leetcode】Remove Duplicates from Sorted Array

原文：http://www.cnblogs.com/MrLJC/p/3664911.html