leetcode题解

最小的K个数

剑指offer的面试题

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

非常简单让人想到的方法就是排序，从小到大排好序之后，然后直接返回前k个元素，此题求解。

实际代码也很简单：

class Solution:
    def getLeastNumbers(self, arr, k:int) :
        a=arr.sort()
        return arr[:k]

list.sort() 方法排序时直接修改原列表，返回None； sorted() 使用的范围更为广泛，但是如果不需要保留原列表。

函数形式如下：

sorted(iterable[, key][, reverse]) 
list.sort(*, key=None, reverse=None)

• key 是带一个参数的函数，返回一个值用来排序，默认为 None。这个函数只调用一次，所以fast。

• reverse 表示排序结果是否反转

  另外就是一种新方法可以用来了解Top-K算法的一种高级用法。改进的快速排序方法， BFPRT算法。

  在BFPTR算法中，仅仅是改变了快速排序Partion中的pivot值的选取，在快速排序中，我们始终选择第一个元素或者最后一个元素作为pivot，而在BFPTR算法中，每次选择五分中位数的中位数作为pivot，这样做的目的就是使得划分比较合理，从而避免了最坏情况的发生。算法步骤如下 ：

  1. 将n 个元素划为 [n/5]组，每组5个，至多只有一组由 n mod 5 个元素组成。
  2. 寻找这 [n/5]个组中每一个组的中位数，这个过程可以用插入排序。

3. 对步骤2中的[n/5] 个中位数，重复步骤1和步骤2，递归下去，直到剩下一个数字。
   4. 最终剩下的数字即为pivot，把大于它的数全放左边，小于等于它的数全放右边。
4. 判断pivot的位置与k的大小，有选择的对左边或右边递归。

求第k大就是求第n-k+1小，这两者等价。

TopK问题最佳的解决思路是使用堆排序:

维护一个小顶堆，保持堆中的元素为k个，依次遍历整个数组中的元素，如果元素超过堆中的数，把顶端的数推出去，直到遍历完整个数组，则堆顶的元素即为topK。

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        int result = 0;
        int numsSize = int(nums.size());
        if (numsSize == 0 || k > numsSize)
        {
            return 0;
        }

        priority_queue<int, vector<int>, greater<int>> store;
        //堆中维持k个最大数
        for (int i = 0; i < numsSize; i++)
        {
            store.push(nums[i]);
            if (int(store.size()) > k)
            {
                store.pop();
            }
        }

        result = store.top();
        return result;
    }
};

其他方法：

• 全局排序，O(n*lg(n))
• 局部排序，只排序TopK个数，O(n*k)
• 堆，TopK个数也不排序了，O(n*lg(k))
• 分治法，每个分支“都要”递归，例如：快速排序，O(n*lg(n))
• 减治法，“只要”递归一个分支，例如：二分查找O(lg(n))，随机选择O(n)
• TopK的另一个解法：随机选择+partition