2020 11/06

剑指 Offer 40. 最小的k个数

题目

思路

思路1：改进的快速排序，对数组快速排序，但是不排完，只选切分到的第k个，也叫快速选择
在这里也复习一下快速排序

快速排序步骤

1. 从数列中取出一个数作为基准数（枢轴pivot）
2. 对数组进行划分(partition)，将比基准数大的元素都移至基准数右边，小于等于基准数的元素移至基准数左边
3. 再对左右的子区间重复第二步的划分操作，直至每个子区间只有一个元素

快排模板代码：

int partition(vector<int> &arr, int left, int right)  { //找基准数 划分
    int i = left + 1 ;
    int j = right;
    int temp = arr[left]; // 第一个数是基准数
    while(i <= j){
        while (i < arr.size() && arr[i] < temp)  i++;// 从左向右找比基准数大的数
        while (j > -1 && arr[j] > temp ) j--;// 从右向左找比基准数小的数
        if (i < j) swap(arr[i++], arr[j--]);// 如果不i在j右边，就交换
        else i++; // ++ 使等于的时候跳出循环
    }
    swap(arr[j], arr[left]); //让基准数到中间
    return j;
}
void quick_sort(vector<int> &arr, int left, int right){
    if (left > right)
        return;
    int j = partition(arr, left, right); // 排序并返回新的中点
    quick_sort(arr, left, j - 1); // 排序左半部分
    quick_sort(arr, j + 1, right); // 排序右半部分
}

快速选择

快速选择基于快速排序，有1个不同点

• 每次不左右两部分都排序，是根据新的中点和k的关系，决定排左边还是排右边

因此在partition的部分无需修改，只需要修改quick_sort部分

void quick_sort(vector<int> &arr, int left, int right, int k){
    if (left > right)
        return;
    int j = partition(arr, left, right); // 排序并返回新的中点
    if(j == k) return;
    if(j > k)
        quick_sort(arr, left, j - 1, k); // 排序左半部分
    else
        quick_sort(arr, j + 1, right, k); // 排序右半部分
}

优先队列实现大顶堆

大顶堆的特点是最顶上的元素是最大的
因此可以实现一个容量是k的大顶堆，方法如下：

• 将前k个数插入堆中
• 从第k+1个数开始，如果第k+1个数比堆顶要小，就把堆顶弹出，然后把数插入堆当中
• 将最好结果转为数组

而 java 和 c++中都有有限队列这个数据结构， 可以用来模拟大顶堆/小顶堆
其使用逻辑为：

• top 访问队头元素
• empty 队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace 原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容

使用时候定义如下：

1 //升序队列，小顶堆
2 priority_queue <int,vector<int>,greater<int> > q;
3 //降序队列，大顶堆
4 priority_queue <int,vector<int>,less<int> >q;

java中也有对应的api

• peek()//返回队首元素
• poll()//返回队首元素，队首元素出队列
• add()//添加元素
• size()//返回队列元素个数
• isEmpty()//判断队列是否为空，为空返回true,不空返回false

创建的代码为

 // Java 的 PriorityQueue 默认是小顶堆，添加 comparator 参数使其变成最大堆
 Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));

实现

class Solution {
public:
    int partition(vector<int> &arr, int left, int right) {
        int i = left + 1 ;
        int j = right;
        int temp = arr[left]; // 第一个数是基准数

        while(i <= j){
            while (i < arr.size() && arr[i] < temp )  i++;// 从左向右找比基准数大的数
            while (j > -1 && arr[j] > temp ) j--;// 从右向左找比基准数小的数
            if (i < j ) swap(arr[i++], arr[j--]);// 如果不i在j右边，就交换
            else i++; // ++ 使等于的时候跳出循环
        }
        swap(arr[j], arr[left]); //让基准数到中间
        return j;
    }

  void quick_sort(vector<int> &arr, int left, int right, int k) {
    if (left > right) return;
    int j = partition(arr, left, right);  // 排序并返回新的中点

    if(j == k) return;
    if(j > k)
        quick_sort(arr, left, j - 1, k); // 排序左半部分
    else
        quick_sort(arr, j + 1, right, k); // 排序右半部分
}


    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        quick_sort(arr, 0, arr.size()-1, k);
        vector<int> res(k);
        for(int i = 0;i < k;i++){
            res[i] = arr[i];
        }

        return res;
    }
};

优先队列实现

class Solution {

public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(k==0) return vector<int>{};
        // 创建堆，并压入前k个
        priority_queue <int,vector<int>,less<int> >q;
        for(int i = 0; i < k;i++){
            q.push(arr[i]);
        }

        // k+1 个后开始比较，比堆顶还小就把堆顶弹出，压入新来的数（排序交给堆）
        for(int i = k;i < arr.size(); i++){
            if(arr[i] < q.top()){
                q.pop();
                q.push(arr[i]);
            }
        }

        // 输出结果
        vector<int> res(k);
        for(int i =0;i <k;i++){
            res[i] = q.top();
            q.pop();
        }

        return res;
    }
};

1046. 最后一块石头的重量

题目

思路

本题在整个过程在，需要不断拿出数据，插入数据，同时每次还需要选出最小的两个
这就很符合堆的特性，将数据放入堆中，让堆进行排序，接下来

• pop出2个数据
• 对这两个数进行碰撞操作
• 将结果push回去

这样就可以完成整个的模拟，例如

1 23 34 46 3

存入堆

pop 2 个堆顶 ----> 46 34  堆 1 23 3

碰撞: 46 - 34 = 8

push 8  ---->  堆 1 23 3 8

实现

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue <int,vector<int>,less<int> >q;
        // 建堆
        for(int i = 0;i < stones.size();i++){
            q.push(stones[i]);
        }

        while(q.size() > 1){
            // 获取两个数
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            // 如果重量不同，把剩下的石头压回去
            if(a != b){
                q.push(a - b);
            }
        }
        if(q.size() == 0) return 0;
        return q.top();
    }
};