《算法进阶50讲》|《算法进阶50讲》K大数算法|排序|堆|哈希|数据结构

文章目录

- 前言
- 一、概念
- 二、排序
- - 1、题目描述
  - 2、算法思路
  - 3、时间复杂度
  - 4、源码分析
- 三、哈希表
- - 1、题目描述
  - 2、算法思路
  - 3、时间复杂度
  - 4、源码分析
- 四、堆
- - 1、题目描述
  - 2、算法思路
  - 3、时间复杂度
  - 4、源码分析
- 五、树状数组
- - 1、题目描述
  - 2、算法思路
  - 3、时间复杂度
  - 4、源码分析
- 六、课后习题

前言一、概念 ????什么是 K 大数？就是给定一些数据，要求求其中第 K 大的数是什么（当然也可以变形，求第 K 小数）。
二、排序前置算法：夜深人静写算法（四十）- 八大排序
1、题目描述

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

2、算法思路
???? ( 1 ) (1) (1) 直接排序，然后取前k k k 个元素就是答案了。
3、时间复杂度
????时间复杂度就是排序的时间复杂度，即O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)。
4、源码分析

class Solution { public: vector getLeastNumbers(vector& arr, int k) { sort(arr.begin(), arr.end()); // (1) while(arr.size() > k) arr.pop_back(); // (2) return arr; } };

???? ( 1 ) (1) (1) 将数组按照递增排序；
???? ( 2 ) (2) (2) 如果元素大于k k k 个，则从尾部剔除；
三、哈希表前置算法：夜深人静写算法（九）- 哈希表
1、题目描述

????给你一个整数数组 nums和一个整数 k，请你返回其中出现频率前 k高的元素。你可以按任意顺序返回答案。

2、算法思路
???? ( 1 ) (1) (1) 首先，将所有数字都映射到哈希表中；
???? ( 2 ) (2) (2) 然后，进行排序，排序关键字有两个：当哈希表中的计数器相等的时候，按照数字本身大小进行递增排序；当计时器不相等的时候，按照每个数字计数的大小进行递减排序；
???? ( 3 ) (3) (3) 最后，从排好序的数组中找出最小的k k k 个不相等的数据；
3、时间复杂度
????哈希表过程的时间复杂度为O ( n ) O(n) O(n)，排序过程的时间复杂度为O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)。
4、源码分析

class Solution { unordered_map hash; public: vector topKFrequent(vector& nums, int k) { hash.clear(); int i; vector ret; for(i = 0; i < nums.size(); ++i) { ++hash[nums[i]]; // (1) } // (2) sort(nums.begin(), nums.end(), [&](const auto& a, const auto&b) { int cnta = hash[a]; int cntb = hash[b]; if(cnta == cntb) { return a < b; } return cnta > cntb; }); ret = { nums[0] }; --k; for(i = 1; i < nums.size() && k; ++i) { if(nums[i] == nums[i-1]) {// (3) continue; } --k; ret.push_back(nums[i]); } return ret; } };

???? ( 1 ) (1) (1) 进行哈希计数；
???? ( 2 ) (2) (2) 实现排序函数，仿函数采用匿名函数；
???? ( 3 ) (3) (3) 每个数字保证只能取一次；
四、堆前置算法：《画解数据结构》（2 - 5）- 堆与优先队列
1、题目描述

????设计一个找到数据流中第k k k 大元素的类。注意是排序后的第k k k 大元素，不是第k k k 个不同的元素。请实现 KthLargest类：
????KthLargest(int k, int[] nums)使用整数k k k 和整数流 nums初始化对象。
????int add(int val)将 val插入数据流 nums后，返回当前数据流中第 k大的元素。

2、算法思路
???? ( 1 ) (1) (1) 对于这个问题，数据一定是越来越多的，也就是如果本身数据排好序以后，第k + 1 k+1 k+1 个元素永远是没有意义的，因为永远不会通过add进行返回；
???? ( 2 ) (2) (2) 基于以上这点，可以实现一个小顶堆，并且不断的弹出元素，直到堆保持k k k 个元素位置；
???? ( 3 ) (3) (3) 每次add操作，就往堆里插入一个元素，并且弹出一个元素，使得堆始终保持k k k 个元素，这样，堆顶的元素就是第k k k 大的元素辣！
3、时间复杂度
????每次插入删除都是O ( l o g 2 n ) O(log_2n) O(log2?n)，查找是O ( 1 ) O(1) O(1) 的，初始化的时间复杂度为O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)。
4、源码分析

class KthLargest { priority_queue , greater<> > q; int K; public: KthLargest(int k, vector& nums) { K = k; while( !q.empty() ) q.pop(); // (1) for(int i = 0; i < nums.size(); ++i) {// (2) add(nums[i]); } }int add(int val) { q.push(val); // (3) while(q.size() > K) {// (4) q.pop(); } return q.top(); } };

???? ( 1 ) (1) (1) 清空数据；
???? ( 2 ) (2) (2) 调用封装好的插入接口；
???? ( 3 ) (3) (3) 将数据插入堆中；
???? ( 4 ) (4) (4) 如果元素个数大于K K K 个，弹出对顶；
五、树状数组前置算法：
???? ( 1 ) (1) (1) 二分枚举
???? ( 2 ) (2) (2) 前缀和
???? ( 3 ) (3) (3) 树状数组
1、题目描述

????设计一个找到数据流中第k k k 大元素的类。注意是排序后的第k k k 大元素(元素范围是[ ? 1 0 4 , 1 0 4 ] [-10^4, 10^4] [?104,104])，不是第k k k 个不同的元素。请实现 KthLargest类：
????KthLargest(int k, int[] nums)使用整数k k k 和整数流 nums初始化对象。
????int add(int val)将 val插入数据流 nums后，返回当前数据流中第 k大的元。

2、算法思路
【《算法进阶50讲》|《算法进阶50讲》K大数】???? ( 1 ) (1) (1) 由于数据范围较小，且存在负数，可以将数据加上一个偏移量后，直接映射到数组中；
???? ( 2 ) (2) (2) 然后每次从大到小统计数组中元素的个数，当出现某一次满足元素总数≥ k \ge k ≥k，说明这个数就是我们要求的第k k k 大数；
???? ( 3 ) (3) (3) 以上算法，插入时间复杂度O ( 1 ) O(1) O(1)，查询时间复杂度O ( k ) O(k) O(k)，所以需要用树状数组优化。
???? ( 4 ) (4) (4) 由于数组统计肯定满足单调性，所以插入可以采用树状数组的插入操作，查找可以用二分查找配合树状数组的求和操作，时间复杂度都保证到O ( l o g 2 n ) O(log_2n) O(log2?n)。
3、时间复杂度
4、源码分析

class KthLargest { #define maxn 20002 #define base 10001 int c[maxn]; int K; void init() { memset(c, 0, sizeof(c)); }int lowbit(int x) { return x & -x; }void treeArrayAdd(int x) { while(x < maxn) { ++c[x]; x += lowbit(x); } }int treeArraySum(int x) { int s = 0; while(x) { s += c[x]; x -= lowbit(x); } return s; }int getKth() { int total = treeArraySum(maxn-1); int l = 1, r = maxn - 1; int ans = 0; while(l <= r) { int mid = (l + r) >> 1; int cnt = total - treeArraySum(mid - 1); // >= mid 的数字有 cnt 个 if(cnt >= K) { ans = mid; l = mid + 1; }else { r = mid - 1; } } return ans; }public: KthLargest(int k, vector& nums) { memset(c, 0, sizeof(c)); K = k; for(int i = 0; i < nums.size(); ++i) { add(nums[i]); } }int add(int val) { treeArrayAdd(val + base); return getKth() - base; } };

六、课后习题

序号	题目链接	难度
1	剑指 Offer 40. 最小的k个数	★☆☆☆☆
2	面试题 17.14. 最小K个数	★☆☆☆☆
3	LeetCode 347. 前 K 个高频元素	★☆☆☆☆
4	LeetCode 692. 前K个高频单词	★☆☆☆☆
5	LeetCode 1985. 找出数组中的第 K 大整数 *	★☆☆☆☆
6	面试题 17.09. 第 k 个数	★★☆☆☆
7	剑指 Offer II 059. 数据流的第 K 大数值	★★☆☆☆
8	703. 数据流中的第 K 大元素	★★☆☆☆
9	LeetCode 440. 字典序的第K小数字 *	★★★★☆