本文共 5107 字，大约阅读时间需要 17 分钟。
有一堆石头，每块石头的重量都是正整数。每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。 示例：输入：[2,7,4,1,8,1]输出：1解释：先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。 提示：1 <= stones.length <= 301 <= stones[i] <= 1000
//优先级队列class Solution { public: int lastStoneWeight(vector & stones) { priority_queue q; for (auto s: stones){ q.push(s); }//元素入队列 while(q.size()>1){ int v1 = q.top(); q.pop(); int v2 = q.top(); q.pop(); if (v1==v2) continue; q.push((v1-v2)); } if (q.empty()) return 0; return q.top(); }}; 输入整数数组 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]
class Solution { public: vector getLeastNumbers(vector & arr, int k) { vector vec(k, 0); if (k == 0) return vec; // 排除 0 的情况 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]); } } for (int i = 0; i < k; ++i) { vec[i] = Q.top(); Q.pop(); } return vec; }}; 复杂度分析
时间复杂度：O(nlogk)，其中 n 是数组 arr 的长度。由于大根堆实时维护前 k 小值，所以插入删除都是 O(logk) 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 O(nlogk) 的时间复杂度。
空间复杂度：O(k)，因为大根堆里最多 k 个数。
设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。示例:int k = 3;int[] arr = [4,5,8,2];KthLargest kthLargest = new KthLargest(3, arr);kthLargest.add(3); // returns 4kthLargest.add(5); // returns 5kthLargest.add(10); // returns 5kthLargest.add(9); // returns 8kthLargest.add(4); // returns 8说明:你可以假设 nums 的长度≥ k-1 且k ≥ 1。
class KthLargest { private class BST { private class TreeNode { private int val; // 结点的count包含自己，所以默认是1 private int count = 1; private TreeNode left; private TreeNode right; TreeNode(int x) { val = x; } } private TreeNode root; public void add(int val) { root = add(root, val); } private TreeNode add(TreeNode node, int val) { if (node == null) { return new TreeNode(val); } if (node.val > val) { node.left = add(node.left, val); } else if (node.val < val) { node.right = add(node.right, val); } // 元素重复 不添加进树但是count++ node.count++; return node; } public TreeNode search(int k) { return search(root, k); } private TreeNode search(TreeNode node, int k) { if (node == null) { return node; } int leftNodeCount = node.left != null ? node.left.count : 0; int rightNodeCount = node.right != null ? node.right.count : 0; int currNodeCount = node.count - leftNodeCount - rightNodeCount; if (k > currNodeCount + rightNodeCount ) { // k > 当前结点数加右子树的结点数，则搜索左子树 return search(node.left, k - currNodeCount - rightNodeCount); } else if (k <= rightNodeCount) { // k <= 右子树的结点数，则搜索右子树 return search(node.right, k); } else { // k == 当前结点数加右子树的结点数，则找到第k大的结点 return node; } } } private int k; private BST bst = new BST(); public KthLargest(int k, int[] nums) { this.k = k; for (int n : nums) { bst.add(n); } } public int add(int val) { bst.add(val); return bst.search(k).val; }} 二叉搜索树
A、利用set自动排序class KthLargest { int K; multiset st;public: KthLargest(int k, vector & nums) { for (int n : nums) { st.insert(n); if (st.size() > k) st.erase(st.begin()); } K = k; } int add(int val) { st.insert(val); if (st.size() > K) st.erase(st.begin()); return *st.begin(); }}; B、堆方法
运用优先级队列
class KthLargest { int K; priority_queue 转载地址：http://gwgwi.baihongyu.com/