数据结构-数组去重

发表于   |   分类于   |     |   阅读次数

给定一个数组，求去掉重复元素后数组的长度。

思路:双指针，设定两个指针i,j分别指向数组的初始的两个元素，当a[i] != a[j],累加j,i保持不变。当a[i]==a[j]，累加i,将a[i]=a[j],再累加j。
双指针的思想，O(n)的时间复杂度。
举例：
A=[1,1,2,3,3,4]
(1) i=0,j=1. a[i]==a[j],j++ 数组元素未变
(2) i=0,j=2, a[i]!=a[j],i++,a[i]=a[j],j++. 数组变为A[1,2,2,3,3,4]
(3) i=1,j=3, a[i]!=a[j],i++,a[i]=a[j],j++. 数组变为A[1,2,3,3,3,4]
(4) i=2,j=4, a[i]==a[j],j++, 数组元素未变
(5) i=2,j=5, a[i]!=a[j],i++,a[i]=a[j],j++, 数组变为A[1,2,3,4,3,4]
(6) j=6 结束循环，此时的i+1即是去重后元素的个数。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
int RemeoveDuplicate(int*a, int size)
{
    int i=0,j;
    for(j=i+1; j<size; ++j)
    {
        if(a[i] != a[j])
        {
            a[++i] = a[j];
        }
    }
    return i+1;
}