算法概论

题目：

2.14 给定一个含有n个元素的数组，注意到数组中的某些元素是重复的，即这些元素在数组中出现不止一次。给出一种算法，以O(nlogn)时间移除掉数组中的所有重复元素。

算法思想：

时间复杂度是O(nlogn)，移除重复元素，可以先将重复元素排到一起，即排序，这里采用归并排序，将数组有序排好，再进行一次扫描，将重复元素删除。时间复杂度为：O（nlogn）+O（n）=O（nlogn）

代码:

#include <iostream>
#include<vector>
constexpr auto INFINITE = 1000000;
using namespace std;
void merge(vector<int>&a, int l1, int r1, int l2, int r2)
{
    int i = l1;
    int j = l2;
    int n = (r1 - l1 + 1) + (r2 - l2 + 1);
    vector<int>temp(n);
    int k = 0;
    while (i <= r1 && j <= r2)
    {
        if (a[i] < a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    while (i <= r1)
        temp[k++] = a[i++];
    while (j <= r2)
        temp[k++] = a[j++];
    for (int i = 0; i < temp.size(); i++)
    {
        a[l1 + i] = temp[i];
    }
}
void MergeSort(vector<int>&a, int Start, int End)//递归
{
    if (Start < End)
    {
        int mid = (Start + End) >> 1;
        MergeSort(a, Start, mid);
        MergeSort(a, mid + 1, End);
        merge(a, Start, mid, mid + 1, End);
    }
}
int main(void)
{
    vector<int>A;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        A.push_back(temp);
    }
    MergeSort(A, 0, A.size() - 1);
    vector<int>result;
    if (A[0] != A[1])
        result.push_back(A[0]);
    for (int i = 1; i < A.size()-1; i++)
    {
        if (A[i] != A[i - 1] && A[i] != A[i + 1])
            result.push_back(A[i]);
    }
    if (A[A.size() - 1] != A[A.size() - 2])
        result.push_back(A[A.size() - 1]);
    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}