删除数组内重复的数据

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

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

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