删除数组内重复的数据

笔试时曾经遇到过的一道题，当时没有好的想法。

今天无意中想起，于是把自己的一种解决方法记下来。

1. main.cpp

/**
 * 问题描述：
 * 删除数组内重复的数据
 *
 * 一个解决方法：
 * 可以先将数组排序，然后再删除
 * 如一个已经排好序的整数数组：1， 1， 2， 2， 3
 */

#include <iostream>

using std::cout;
using std::endl;
using std::swap;

/**
 * 打印数组
 */
template<class T>
void printArray(const T array[], const int size);

/**
 * 将数组排序，选择排序
 */
template<class T>
void sort(T array[], const int size);

/**
 * 对已经排好序的数据
 * 将数组内重复的数据删除
 * @return int 删除重复数据后数组的大小
 */
template<class T>
int deleteRepeatedData(T array[], const int size);

int main(int argc, char *argv[]) {
    int array[] = {9, 1, 1, 8, 2, 3, 3, 4, 3, 3, 5, 9, 7, 8, 2, 6, 9, 1, 9, 0, 9, 0};
    int size = sizeof(array) / sizeof(int);
    cout<<"A initial int array: "<<endl;
    printArray(array, size);
    
    cout<<"\nAfter sort: "<<endl;
    sort(array, size);
    printArray(array, size);

    cout<<"\nAfter delete repeated data: "<<endl;
    size = deleteRepeatedData(array, size);
    printArray(array, size);
}

/**
 * 打印数组
 */
template<class T>
void printArray(const T array[], const int size) {
    for (int i=0; i<size-1; i++) {
        cout<<array[i]<<", ";
    }
    cout<<array[size-1]<<endl;
}

/**
 * 将数组排序，选择排序
 */
template<class T>
void sort(T array[], const int size) {
    for (int i=0; i<size-1; i++) {
        int min = i;
        for (int j=i+1; j<size; j++) {
            if (array[min] > array[j]) {
                min = j;
            }
        }
        if (min != i) {
            swap(array[i], array[min]);
        }
    }
}

/**
 * 对已经排好序的数据
 * 将数组内重复的数据删除
 * @return int 删除重复数据后数组的大小
 */
template<class T>
int deleteRepeatedData(T array[], const int size) {
    int j = 0;
    for (int i=0; i<size-1; i++) {
        while (array[i] == array[i+1]) {
            i++;
        }
        array[j++] = array[i];
    }
    return j;
}

 

2. main.cpp download

注：发表于： 2008-11-10 ，修改于： 2009-05-16 13:24，chinaunix

评论

2 楼 finux 2010-04-21  

cnSpirit 写道

我没怎么看明白，呵呵。
那个，既然是数组的话，你怎么能够删除掉元素呢？
第86行这个函数改变不了数组长度吧？
而且89行的代码是不是会造成下标越界呢？
比如传入数组=[1,1,1]，size=3时候，在for循环i=0时候，while循环动作如下：
1.  i=0,array[0]=array[1], i++
2.  i=1,array[1]=array[2], i++
3.  i=2,array[2]=array[3??]...


对了finux，我刚刚签了一家公司，无忧创想，www.51cto.com，做网站的，呵呵

恭喜恭喜！牛X，请吃饭哦，嘻嘻。。。
注意deleteRepeatedData要返回经过删除操作的数组的大小。事实上数组的大小并没有改变，只是把没有重复数据往前排，然后再把没有重复的数据的大小返回。这样，其实就是把重复的数据删除了嘛。若是有更OK的方式，欢迎一起讨论哦~

1 楼 cnSpirit 2010-04-21  

我没怎么看明白，呵呵。
那个，既然是数组的话，你怎么能够删除掉元素呢？
第86行这个函数改变不了数组长度吧？
而且89行的代码是不是会造成下标越界呢？
比如传入数组=[1,1,1]，size=3时候，在for循环i=0时候，while循环动作如下：
1.  i=0,array[0]=array[1], i++
2.  i=1,array[1]=array[2], i++
3.  i=2,array[2]=array[3??]...


对了finux，我刚刚签了一家公司，无忧创想，www.51cto.com，做网站的，呵呵