HJ3.明明的随机数

解法一(偷懒解法）：

#include <iostream>
#include <string>
#include <set>

int main(int argc, const char * argv[]) {
    int n, num;
    std::set<int> nums;
    while (std::cin >> n) {
        while (n--) {
            std::cin >> num;
            nums.insert(num);
        }
        for (auto& i : nums) {
            std::cout << i << std::endl;
        }
        nums.clear();
    }
    return 0;
}

解法二：

#include <iostream>
#include <string>
#include <vector>

void swap(std::vector<int>& nums, int a, int b) {
    int sz = (int)nums.size();
    if (a != b && (a > 0 && a < sz) && (b > 0 && b < sz)) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}

void deal_pivot(std::vector<int>& nums, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        if (nums[l] > nums[m]) {
            swap(nums, l, m);
        }
        if (nums[l] > nums[r]) {
            swap(nums, l, r);
        }
        if (nums[r] < nums[m]) {
            swap(nums, r, m);
        }
        swap(nums, m, l);
    }
}

int part(std::vector<int>& nums, int l, int r) {
    int pivot = nums[l];
    while (l < r) {
        while (l < r && nums[r] >= pivot) {
            --r;
        }
        nums[l] = nums[r];
        while (l < r && nums[l] <= pivot) {
            ++l;
        }
        nums[r] = nums[l];
    }
    nums[l] = pivot;
    return l;
}

void quick_sort(std::vector<int>& nums, int l, int r) {
    if (l < r) {
        int pivot = part(nums, l, r);
        quick_sort(nums, l, pivot - 1);
        quick_sort(nums, pivot + 1, r);
    }
}

void make_uniq(std::vector<int>& nums) {
    quick_sort(nums, 0, (int)nums.size() - 1);
    
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i - 1] == nums[i]) {
            nums.erase(nums.begin() + i);
            --i;
        }
    }
}

int main(int argc, const char * argv[]) {
    int n, num;
    std::vector<int> nums;
    while (std::cin >> n) {
        while (n--) {
            std::cin >> num;
            nums.emplace_back(num);
        }
        make_uniq(nums);
        for (auto& i : nums) {
            std::cout << i << std::endl;
        }
        nums.clear();
    }
    return 0;
}

解题思路：

难点1：如果在允许使用库的情况下，重点在于能不能想到利用set排序去重；

难点2：这道题被标记为了较难，使用set库的话就失去了题目本身的意义，更多地，题目在考察答题者能否手撕排序算法。这里使用的快排算法，也是最常被问到的。deal_pivot只是对枢轴值的一个中位数优化，可以不用关注，唯一需要记忆的就quick_sort算法本身的递归结构和最核心的part函数。,quick_sort函数体本身不用记忆，理解后自然就记住了，part函数就那么几行，没啥好办法，理解了之后背就完事；

int part(std::vector<int>& nums, int l, int r) {
    int pivot = nums[l];
    while (l < r) {
        while (l < r && nums[r] >= pivot) {
            --r;
        }
        nums[l] = nums[r];
        while (l < r && nums[l] <= pivot) {
            ++l;
        }
        nums[r] = nums[l];
    }
    nums[l] = pivot;
    return l;
}

void quick_sort(std::vector<int>& nums, int l, int r) {
    if (l < r) {
        int pivot = part(nums, l, r);
        quick_sort(nums, l, pivot - 1);
        quick_sort(nums, pivot + 1, r);
    }
}

难点3：set的使用，很久不用会忘记方法；

知识点：

知识点1：unordered_set与set的区别；

unordered_set基于哈希表，是无序的。

set实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。

知识点2：set与vector的转换；

#include <set>
#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> vec;
    vec = { 1, 2, 3, 4, 8, 9, 3, 2, 1, 0, 4, 8 };
    set<int> st(vec.begin(), vec.end());
    vec.assign(st.begin(), st.end());

    for (auto& i : vec) {
        cout << i << endl;
    }
    
    return 0;
}

知识点3：快排是一种不稳定的排序算法；核心思想是通过与枢轴值的比较，将比枢轴值小的放在左侧，大的放在右侧，以此二分下去。