今年找实习的时候刷题做到了一道很热门的考题——取数组前k大的数。

    这道题是一道思路并不困难的题目，拿到题目的第一眼我就明白最好的解决方法就是先对数组进行排序，再取前k大的值即可。这道题和 LeetCode 215. 数组中的第K个最大元素 基本一致，所以此处可以用这道题目来讲解。

    1. 215. 数组中的第K个最大元素
    2. 在未排序的数组中找到第 k 个最大的元素。
    3. 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    4. 示例 1:  输入: [3,2,1,5,6,4] 和 k = 2   输出: 5   
    5. 示例 2:  输入: [3,2,3,1,2,4,5,5,6] 和 k = 4   输出: 4
    6. 说明: 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

    当时在解题的过程中，我使用了最简单的方法，就是使用STL的 sort() 方法。使用 sort() 之后，整个解题非常简单，只需要两三行代码即可。

    1. class Solution {
    2. public:
    3.     int findKthLargest(vector<int>& nums, int k) {
    4.         sort(nums.begin(), nums.end());
    5.         return nums[nums.size() - k];
    6.     }
    7. };

    但是面试的时候肯定不是让我来耍STL的函数的，本道题目实际上考的就是如何对数组进行排序。排序在数据结构的课上就学过很多种方法，比较简单的例如选择排序、插入排序、冒泡排序等都是常用的排序方法，而快速排序、堆排序、希尔排序、归并排序这些较为复杂的排序法才是在面试笔试过程中比较容易考到的。所以此处我以快速排序和堆排序为例来展示如何解决这道问题。

    1. class Solution {
    2. public:
    3.     /* 快排思想的步骤：
    4.     1. 随机确定一个基准值 
    5.     2. 小数放左，大数放右 
    6.     3. 检查当前值的位置 
    7.        等于 k-1 当前数就是第K大 target
    8.        小于 k-1 target在右区间
    9.        大于 k-1 target在左区间
    10.     4. 在目标区间继续寻找 */
    11.     int findKthLargest(vector<int>& nums, int k) {
    12.         int n = nums.size(), start = 0, end = nums.size() - 1;
    13.         return findFunction(nums, n - k, start, end);
    14.     }
    16.     int findFunction(vector<int>& nums, int k, int start, int end){
    17.         int p = rand() % (end - start + 1) + start; // 随机取一个基准
    18.         swap(nums[p], nums[end]);
    19.         p = end; // 将基准放在最后一个位置
    20.         int curVal = nums[p], left = start, right = end - 1;
    22.         if (start == end && start == k) 
    23.             return nums[start]; // 如果相等，则当前数就是第K大 target
    25.         while(left < right){ // 循环找到left和right符合条件的值并交换
    26.             while(left < right && nums[left] < curVal)
    27.                 left ++; // 若小于则增加left
    29.             while(left < right && nums[right] >= curVal)
    30.                 right--; // 若大于则减小right
    32.             if(left < right)
    33.                 swap(nums[left], nums[right]); // 只要left小于right，则交换left和right下标的数值
    34.         }
    36.         if (nums[right] < curVal) 
    37.             right++; // 如果此时right的值还是小于curVal则将right再加一
    38.         swap(nums[right], nums[end]); // 交换right和end的值
    39.         p = right; // 将p指向right
    40.         if(p == k) // 若p就等于k，则说明当前值就是第k大的值
    41.             return nums[p];
    42.         // 若小于则说明target的值在当前的右边区间，若小于则target在当前的左边区间
    43.         return p < k ? findFunction(nums, k, right+1, end) : findFunction(nums, k, start, right-1);
    44.     }
    45. };

    以上是使用快排的方法进行排序。快排的方法最大的缺点是 不容易记住 在基本有序的情况下，会出现很消耗极大的时间的情况，但是平均性能较好，时间复杂度是O(N * log K)。然后接下来是一个在数据结构课上并没有着重介绍的堆排序的方法。

    堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。建立一个大根堆，做 k − 1 次删除操作后堆顶元素就是我们要找的答案。虽然使用优先队列可以直接实现堆容器的建立，但是面试时能自己建立大顶堆则是一个明显的加分项

    1. class Solution {
    2. public:
    3.     void maxHeapify(vector<int>& a, int i, int heapSize) { // 首先定义大顶堆的排序操作
    4.         int left = i * 2 + 1, right = i * 2 + 2, largest = i;
    5.         if (left < heapSize && a[left] > a[largest])
    6.             largest = left; // 将最大值的下标定在左边
    7.         if (right < heapSize && a[right] > a[largest])
    8.             largest = right; // 将最大值的下标定在右边
    9.         if (largest != i) {
    10.             swap(a[i], a[largest]); // 交换最大值与下标i的值
    11.             maxHeapify(a, largest, heapSize);
    12.         }
    13.     }
    15.     void buildMaxHeap(vector<int>& a, int heapSize) { // 建立大顶堆
    16.         for (int i = heapSize / 2; i >= 0; i --)
    17.             maxHeapify(a, i, heapSize); // 从数组的中间值开始，每个进行操作
    18.     }
    20.     int findKthLargest(vector<int>& nums, int k) {
    21.         int heapSize = nums.size(); // 获取堆的长度大小
    22.         buildMaxHeap(nums, heapSize); // 首先进行大顶堆的建立
    23.         for (int i = nums.size() - 1; i >= nums.size() - k + 1; i --) {
    24.             swap(nums[0], nums[i]); // 交换首位和第i位的值
    25.             heapSize --; // 堆的长度减一
    26.             maxHeapify(nums, 0, heapSize); // 从第0位开始，进行堆排序的操作
    27.         }
    28.         return nums[0];
    29.     }
    30. };
    32. // 作者：LeetCode-Solution

    堆排序的时间复杂度为 O(N logN)，但堆排序存在一个很大的问题 —— 堆的维护问题，实际场景中的数据是频繁发生变动的，而对于待排序序列的每次的增删改查回导致堆的维护需要重新进行一次，这在大多数情况下都是没有必要的。所以我们在实际情况中基本使用的还是快速排序。

    在我们本学期学习的软件工程大作业中，我们做了一个缘分匹配系统。缘分匹配系统，自然需要进行一个基础的匹配。但是匹配是存在一定难度的，因为我们后端只会一些基础的操作，很难根据同学自己写入的自我介绍分割关键词并进行加权匹配。所以我们采取了一个很简单但是很好用的方法，就是将每一个同学建立一个匹配编码，该编码仅包括1和0。例如下图，在同学感兴趣的方面我们则设置为 1，不感兴趣的方面则设置为 0。

    1.png

    所以我们可以获得每个人都有一个用于匹配的编码。例如Jack可以根据他的填写获得的匹配码为 1010 1001 0011，而Rose根据填写获得了 1101 1111 0001。所以使用按位 同或 xnor （也可以使用 与 and ） 操作，可以获得Jack和Rose之间有哪些共同的兴趣点。
    若是对Jack进行匹配，则先让Jack的匹配码与每位同学的匹配码进行匹配，获得一个匹配后的值。每个进行匹配的同学与Jack都会有一个匹配值，此时只要对匹配值进行一个排序，再筛选出前8大的值，即可找出与Jack最匹配的8位同学。这个方法的好处就在于匹配简单，比较适合我这样没有深度学习基础和能力的同学在完成课设作业的时候使用。但在实际应用当中肯定是无法像这样随意进行匹配的，为了更准确地进行匹配，我们的课设作业中出现了将近一百个兴趣选择，实际操作中，这肯定是一个不切实际的选项。

    2.jpg

    所以此时在编写代码的过程中就发现，取前K大的值其实是一个非常常用的算法问题，而快排则是一个非常好的解决方案，网上对快排有很多种优化的方案，最优秀的方案可以把时间复杂度降低到O(N)，此处暂略不表。