一、前言

最近在复习王道老师的《数据结构考研复习指导》这本书，第2章线性表的课后题，有一题比较有意思：

从有序顺序表中删除删除所有其值重复的元素，使表中所有元素的值均不同

从有序的顺序表中去除重复元素还是很简单的，但是，如果从无序的顺序表中去重要怎么实现呢？下面分享一下我的解题思路

二、解题思路

思路1

其实可以先给无序的顺序表做个排序，变成有序的顺序表，也就是“降维打击”，按照有序顺序表的方法做即可。

思路2

换个思路，如果学过Python的同学，应该会知道Python里有一个操作：

key in dict

如果键key在字典dict里（这里的字典也可以是列表、数组等），则返回true，否则返回false。

而在C++中，并没有这样的操作，所以我的思路就是在C++中实现这样的操作，以此判断是否有重复的元素。

接下来就简单了，假设待去除的是数组A，我们新建一个数组B用来存放不重复的元素，然后遍历数组A中的所有元素，如果数组A中的第i个元素不在数组B中，则把该元素添加到数组B中。然后重复这个操作，直到数组A遍历结束。

下面我们来看一下怎么用代码实现这个思路。

三、代码实现

为了保存我在学习过程中写的代码，我在GitHub上开了一个仓库，欢迎大家互相学习：

• https://github.com/zbp-xxxp/start_c_plus_plus

今天的这段代码也已经上传，保存在start_c_plus_plus/test/deduplication.cpp

1.判断元素是否在数组中

bool repeat(int *List, int num) {
    int List_length = sizeof(List)/sizeof(int); // 数组长度
    for (int i=0; i<=List_length; i++) {
        if (List[i] == num) { // 判断数组内是否存在元素num
            return true; // 存在，则返回ture
        }
    }
    return false; // 不存在，则返回false
}

2.主函数

int main() {
    int List[10] = {10, 1, 1, 10, 2, 1, 3, 2, 1, 10}; // 自定义一个待排序数组
    int new_List[10]; // 新建一个数组用来存放去重后的元素
    new_List[0] = List[0]; // 原数组中第一个元素肯定是不会重复的
    int j = 1; // 从第2个（索引J+1）开始存储不重复元素
    int List_length = sizeof(List)/sizeof(int); // 数组长度
    for (int i=1; i<List_length; i++) { // 遍历原数组中每个元素
        if (repeat(new_List, List[i]) == false) { // 判断 原数组 中第i个元素是否在 存储不重复元素的数组中
            new_List[j] = List[i]; // 不存在，则将原数组中第i个元素存放在 存储不重复元素的数组中的第j个索引里
            j++;
        }
    }
}

3.完整代码

我们结合上面的代码，加上头文件，并且为了直观地检验算法的正确性，我们可以加上输出。

#include<iostream>
using namespace std;

bool repeat(int *List, int num) {
    int List_length = sizeof(List)/sizeof(int); // 数组长度
    for (int i=0; i<=List_length; i++) {
        if (List[i] == num) { // 判断数组内是否存在元素num
            return true; // 存在，则返回ture
        }
    }
    return false; // 不存在，则返回false
}

int main() {
    int List[10] = {10, 1, 1, 10, 2, 1, 3, 2, 1, 10}; // 自定义一个待排序数组
    // 下面4行用来输出待去除数组
    cout << "去重前：" << endl;
    for (int i=0; i<10; i++) {
        cout << List[i] << " ";
    }cout << endl;

    int new_List[10]; // 新建一个数组用来存放去重后的元素
    new_List[0] = List[0]; // 原数组中第一个元素肯定是不会重复的
    int j = 1; // 从第2个（索引J+1）开始存储不重复元素
    int List_length = sizeof(List)/sizeof(int); // 数组长度
    for (int i=1; i<List_length; i++) { // 遍历原数组中每个元素
        if (repeat(new_List, List[i]) == false) { // 判断 原数组 中第i个元素是否在 存储不重复元素的数组中
            new_List[j] = List[i]; // 不存在，则将原数组中第i个元素存放在 存储不重复元素的数组中的第j个索引里
            j++;
        }
    }

    // 下面4行用来输出已去重数组
    cout << "去重后：" << endl;
    for (int i=0; i<j; i++) {
        cout << new_List[i] << " ";
    }cout << endl;
    return 0;
}

输出如下：

去重前：
10 1 1 10 2 1 3 2 1 10 
去重后：
10 1 2 3 

四、总结

最后总结一下吧，算一下算法的时间复杂度。

假设待去除的数组长度为n，那么判断元素是否在数组中的函数时间复杂度是$O(n)$，主函数里会调用该函数n-1次，所以程序的时间复杂度应该是$O(n^2)$。