投稿
  1. 首页
  2. 随笔

LeetCode

十字消除 • 2022-11-16 • 随笔 • 阅读 12

LeetCode,第1张

LeetCode

目录

一，题目描述

英文描述

中文描述

示例与说明

二，解题思路

1，手动实现堆——C++泛型实现

2，手动实现堆——java泛型实现

3，快速使用堆——C++

优先队列

pop_heap()、push_heap()

4，快速使用堆——java

三，AC代码

C++

Java

四，解题过程

第一博

一，题目描述 英文描述

English description is not available for the problem. Please switch to Chinese.

中文描述

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

示例与说明

限制：

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

来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路

很明显这一题可以采用堆来实现。

通常堆的实现是基于完全二叉树的，也就是说可以创建一个数组，并利用下标定位子节点或父节点。

堆可以分为两种：大根堆（根节点最大），小根堆（根节点最小）。

堆的 *** 作主要分两种（以大根堆为例）：

  • pop：将头节点d出，从左右节点选出较大者填补空缺，迭代完成后续 *** 作。这一过程是自上而下完成的，可以看作sift_down；
  • push：将节点插入到数组末尾，不断和其父节点比较并替换，迭代完成后续 *** 作。这一过程是自下而上完成的，可以看作sift_up；

说起来容易，但是要想实现功能较为完整的堆，并灵活的运用到题目中去，还需要借助泛型编程的力量。

1，手动实现堆——C++泛型实现

参考@AlexanderGan【堆__C++泛型实现简易的优先队列】，这里对算法实现的具体细节略作修改。

#include
#include
#include
#include

using namespace std;

template
// 小根堆，Greater可以理解为后面的数据越来越大
class Greater {
public:
    // true：参数2优先级高，false：参数1优先级高。与C++中的设计保持一致
    bool operator() (const T& a, const T&b) {
        return a > b;
    }
};

template
class MyHeap {
private:
    vector data;

private:
    // 从当前位置pos向下筛选，和子节点中优先级最高的对比，判断是否继续向下
    void siftDown (int pos) {
        int i = pos * 2 + 1;                // 左子节点
        while (i < data.size()) {
            if (i + 1 < data.size() && CMP()(data[i], data[i + 1])) {
                i++;                        // 选出优先级较高的位置
            }
            if (CMP()(data[pos], data[i]) == false) {
                // 当前节点优先级高于任意子节点，不需要继续向下判断
                break;
            } else {
                // 选择优先级较高的节点替换当前位置pos，继续向下判断
                swap(data[i], data[pos]);
                pos = i;
                i = pos * 2 + 1;
            }
        }
    }

    // 从当前位置pos向上筛选，和父节点对比，判断是否继续向上
    void siftUp (int pos) {
        // 父节点存在，且当前节点优先级高于父节点
        while ((pos - 1) / 2 >= 0 && CMP()(data[(pos - 1) / 2], data[pos])) {
            swap(data[pos], data[(pos - 1) / 2]);
            pos = (pos - 1) / 2;
        }
    }

public:
    T top () {
        if (data.size() > 0) return data[0];// 堆的下标从0开始
        return INT_MIN;                     // 用最大或最小值标记非法输出
    }
    void push (T x) {
        data.push_back(x);
        siftUp(data.size() - 1);
    }
    void pop () {
        data[0] = data[data.size() - 1];    // 把最后一个元素移到数组头部，将其覆盖
        data.pop_back();                    // 将数组尾部的元素d出
        siftDown(0);                        // 自上而下调整各个节点
    }
    int size() {
        return data.size();
    }

};

int main() {
    MyHeap > myHeap;
    myHeap.push(1); 
    myHeap.push(3);
    myHeap.push(2);
    myHeap.push(6);
    myHeap.push(4);
    myHeap.push(5);
    myHeap.push(8);
    myHeap.push(7);
    myHeap.push(9);

    while (myHeap.size()) {
        cout< 

 
2，手动实现堆——java泛型实现 

C++中可以无脑使用vector来存储数据。Java一般用ArrayList或linkedList。
 

  • 由于堆需要频繁的d出数组中的元素，ArrayList作为连续数组的一种实现方式，显然不是很好的选择（连续数组删除元素后，为保持正确性，需要移动后面的元素来填补空缺）；
  • linkedList虽然可以方便的实现节点的删除，但是无法利用索引位置定位，效率也比较低下；


因此这里直接采用数组形式来实现数据存储，这样需要自己控制数组的容量并记录当前数组的元素数目。
 

具体实现参考@艾黛尔贾特【使用 Java 实现优先队列（小根堆）】，大佬写的很详细，还包括了扩容算法，这里为了简化代码就没加上这部分。
 

 
 
知识补充
 
 
@成长的小菜鸟【接口作为类型使用】https://blog.csdn.net/weixin_35756522/article/details/77016987https://blog.csdn.net/weixin_35756522/article/details/77016987@唯一浩哥【Java基础系列-Comparable和Comparator】https://www.jianshu.com/p/f9870fd05958https://www.jianshu.com/p/f9870fd05958】" data-link-title="@小米干饭【如何理解 Java 中的 >】">@小米干饭【如何理解 Java 中的 >】https://www.cnblogs.com/xiaomiganfan/p/5390252.html">>】" data-link-title="@小米干饭【如何理解 Java 中的 >】">@小米干饭【如何理解 Java 中的 >】https://www.cnblogs.com/xiaomiganfan/p/5390252.htmlhttps://www.cnblogs.com/xiaomiganfan/p/5390252.html
 

 

// 类型E或E的父类必须实现Comparable接口中的compareTo方法
public class MyHeap > {
    private static final int DEFAUT_CAPACITY = 100;// 设置数组默认大小
    private int currentSize;// 表示当前堆的大小
    private E[] data;// 存放数据

    
    public MyHeap() {
        data = (E[]) new Comparable[DEFAUT_CAPACITY];
        currentSize = 0;
    }

    
    private void swap (int i, int j) {
        E tem = data[i];
        data[i] = data[j];
        data[j] = tem;
    }

    
    private void siftUp (int pos) {
        int fatIndex = (pos - 1) / 2;// 从数组下标0开始存放数据，所以计算父节点位置需要先减一
        // 下标未越界且当前节点优先级高于父节点
        while (fatIndex >= 0 && data[pos].compareTo(data[fatIndex]) > 0) {
            swap(pos, fatIndex);
            pos = fatIndex;
            fatIndex = (pos - 1) / 2;
        }
    }

    
    private void siftDown (int pos) {
        int childIndex = pos * 2 + 1;
        while (childIndex < currentSize) {
            // 下标未越界且右子节点优先级高于左子节点
            if (childIndex + 1 < currentSize && data[childIndex + 1].compareTo(data[childIndex]) > 0) {
                childIndex++;
            }
            // 当前节点优先级高于任意子节点，停止向下筛选
            if (data[pos].compareTo(data[childIndex]) > 0) {
                break;
            } else {
                swap(pos, childIndex);
                pos = childIndex;
                childIndex = pos * 2 + 1;
            }
        }
    }

    public int size() {return currentSize;}

    public E top() {return currentSize > 0 ? data[0] : null;}

    public void push(E e) {
        if (currentSize == DEFAUT_CAPACITY) {
            System.out.println("数据溢出，请重新设置默认容量");
            return;
        }
        data[currentSize++] = e;
        siftUp(currentSize - 1);
    }

    public void pop() {
        if (currentSize == 0) {
            System.out.println("暂无数据");
            return;
        }
        data[0] = data[--currentSize];// 将最后一个元素填充到空出来的位置
        siftDown(0);// 向下筛选
    }
}

 

 

 
 
如何理解C++和Java中的比较器？（参考@蓦子骞【小根堆的建立与比较器】）
 
 
  • 如果comparator返回值为false，可理解为operator *** 作无效，a和b的顺序和形参表中一样，a依旧在前，b在后；
  • 若返回值为true, operator *** 作有效，交换ab位置，b在前（即更“大”）；


 
3，快速使用堆——C++ 

主要有两种方法，一种是直接使用优先队列，另一种是借助pop_heap()、push_heap()实现。
 
优先队列 

参考@AAMahone【C++ priority_queue的自定义比较方式】
 

优先队列的这个类型，其实有三个参数：priority_queue，即类型，容器和比较器，后两个参数可以缺省，这样默认的容器就是vector，比较方法是less，也就是默认大根堆(less对应大根堆！！！表示元素越来越小)，可以自定义写比较方法，但此时若有比较方法参数，则容器参数不可省略！priority_queue<>的可支持的容器必须是用数组实现的容器，如vector，deque，但不能是list（推荐vector），比较方法可以写结构体重载()运算符，也可以用less，greater这些语言实现了的，但是灵活性不够，建议手写重载结构体，或者——如果不想写比较结构体的话，就将后面的两个参数缺省，直接重载类型的<运算符
 

priority_queue Q;
for (int i = 0; i < k; ++i) {
    Q.push(arr[i]);
}
for (int i = k; i < (int)arr.size(); ++i) {
    if (Q.top() > arr[i]) {
        Q.pop();
        Q.push(arr[i]);
    }
}
// -------------------------------------
struct cmp {
    bool operator()(node a, node b) {
        return a.val < b.val;
    }
};
priority_queue, cmp> Q;
 
pop_heap()、push_heap() 

vector nums = { 4, 5, 1, 3, 2 ,8 ,7};
make_heap(nums.begin(), nums.end(),less());
cout << "initial max value : " << nums.front() << endl;
// pop max value
pop_heap(nums.begin(), nums.end());
// push a new value
nums.push_back(6);
push_heap(nums.begin(), nums.end());
 

 
4，快速使用堆——java 

下面的方法在leetcode上可以直接使用，但是在IDEA中会报错，不晓得是哪里的问题（jdk1.8版本太低了？）
 

PriorityQueue queue = new PriorityQueue(new Comparator() {
    // 大根堆    
    public int compare(Integer num1, Integer num2) {
        return num2 - num1;
    }
});
queue.offer(x);// 相当于push
queue.poll();// 相当于pop
queue.peek();// 相当于top

 

 
三，AC代码 
C++ 

class Solution {
public:

    vector getLeastNumbers(vector& arr, int k) {
        priority_queue, less> heap;
        vector ans(k);
        for (int x : arr) {
            heap.push(x);
            if (heap.size() > k) heap.pop();
        }
        for (int i = 0; i < k; i++) {
            ans[i] = heap.top();
            heap.pop();
        }
        return ans;
    }
};
 
Java 

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue heap = new PriorityQueue<>(new Comparator(){
            public int compare (Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            heap.offer(arr[i]);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = heap.peek();
            heap.poll();
        }
        return ans;
    }
}
 
四，解题过程 
第一博 

优先队列，没什么好说的，记录下手写首先队列的方法，以备万一
 

 

					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5097587.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
十字消除 十字消除 一级用户组
0 0
上一篇 2022-11-16
下一篇 2022-11-16

发表评论

登录后才能评论

评论列表（0条）

保存