1. 数组，查找第k大值
215. 数组中的第K个最大元素（元素不重复无序） Kth Largest Element in an Array medium
法1. 算法复杂度O(nlogn)，空间复杂度O(1)
先把数组排序，取nums[nums.length-k]
法2. 算法复杂度O(nklogk)，空间复杂度O(k)
使用 小顶堆PriorityQueue，堆大小为k，每个值入队列，如果超过k，则出队列poll()(出最小值)，最后堆内的peek()就是第k大的值
法3. 算法复杂度O(n)~O(n^2)，空间复杂度O(1)
利用中序遍历的partition可以快速定位到中间值，通过对比中间值下标和k**，可以决定方向
考虑下数组中的第K个最大元素（元素重复无序）如何解决
设置k大小的数组，
每次新插入值用二分查找，如果重复，结束，否则大于且大于最小值，插入对应位置，并出最小值，位移用内存拷贝（这里可以认为没有时间损耗）
时间复杂度是O(nlogk)
2. 数组，查找出现频率前k的值
347. 前K个高频元素 Top K Frequent Elements medium
法1. 时间复杂度O(nlogn) 空间复杂度O(n)
用map存储词-词频，用大根堆进行过滤
法2. 时间复杂度O(n) 空间复杂度O(n)
用map存储词-词频，用bucket[] 下标存储词频，值存储词
692. 前K个高频单词 Top K Frequent Words medium
法1. 时间复杂度O(nlogk) 空间复杂度O(n)
用map存储词-词频，用大根堆进行过滤
3. 树，查找第k小值
230. 二分查找数查找第k小的值 Kth Smallest Element in a BST medium
法1. 时间复杂度O(n), 空间复杂度O(n)
由于树有序，先中序遍历出List<>，然后取第k个
法2. 时间复杂度O(k), 空间复杂度O(1)
回溯，由于树有序，按中序遍历找到最左节点（最小节点），每中/后遍历一次k--，当k被减为0，说明找到第k小的(不会再回溯)
但是这种采用递归的方法，不会因为找到目标而结束递归
详解
4. 数组，按照字符出现的频率进行排序
451. 根据字符出现频率排序(频率高的排列在前方) Sort Characters By Frequency medium
法1. 时间复杂度O(nlogn)，空间复杂度O(n)
使用堆排序，小顶堆
法2. 时间复杂度O(n)，空间复杂度O(n)
使用bucket[]，下标为字符出现个数，值为字符
5. 字符第一个唯一的字符下标
387. 字符串中的第一个唯一字符 First Unique Character in a String
法1. 时间复杂度O(n)，空间复杂度O(n)
先保存每个字符出现的频率，再遍历判断字符出现频率等于1的立即return
6. 传入一维数组，业务处理，返回最大值
561. 数组拆分 I Array Partition I easy
先用Arrays.sort(); 对数组做双向快排有序，然后step=2的跳数组，取两两最小值
网友评论