算法练习：两指针之有序数组去重

问题描述

给出一个有序数组，就地移除重复元素，保持每个元素只出现一次，并返回新数组的长度。

问题分析

这个比较简单，直接使用两个指针，一个在前，一个在后，扫描一遍数组即可。时间复杂度为O(n^2)。

比如数组A = { 1，1， 2， 3， 3 }，看下图，思想简单明了。

代码实现

#include <iostream>

using namespace std;


//去除数组中重复的数字，返回新数组的长度
int RemoveDuplicate( int nArray[], int nCount )
{
  int i = 0;
  int j = i + 1;
  for( ; j < nCount; ++j )
  {
    //j在i的前面走
    //如果两者值不同，则在i+1位置保存j位置的数值
    if( nArray[i] != nArray[j] )
    {
      nArray[++i] = nArray[j];
    }
  }

  return i + 1;
}


int main()
{
  int nArray[] = { 1, 1, 2, 3, 3 };
  int nLen = RemoveDuplicate( nArray, _countof( nArray ) );

  for( int i = 0; i < nLen; ++i )
  {
    cout << nArray[i] << " ";
  }
  cout << endl;

  return 0;
}

系列文章说明:
1.本系列文章[算法练习],仅仅是本人学习过程的一个记录以及自我激励,没有什么说教的意思。如果能给读者带来些许知识及感悟，那是我的荣幸。
2.本系列文章是本人学习陈东锋老师《进军硅谷，程序员面试揭秘》一书而写的一些心得体会，文章大多数观点均来自此书，特此说明！
3.文章之中,难免有诸多的错误与不足,欢迎读者批评指正,谢谢.

作者：山丘儿