LeetCode刷题笔记（3）

背景

今天主要是刷了两道kth排序的题目，中等难度，主要运用了HashMap，还是比较难的，主要考虑java中映射的概念。

215、在未排序的数组中找到第 k 个最大的元素。

方法一：基于快速排序的选择方法 快速排序算法过程： 分解： 将数组 a[l⋯r] 「划分」成两个子数组a[l⋯q−1]、a[q+1⋯r]，使得a[l⋯q−1] 中的每个元素小于等于 a[q]，且a[q] 小于等于 a[q+1⋯r] 中的每个元素。其中，计算下标 q 也是「划分」过程的一部分。 解决： 通过递归调用快速排序，对子数组]a[l⋯q−1] 和 a[q+1⋯r] 进行排序。 合并： 因为子数组都是原址排序的，所以不需要进行合并操作，a[l⋯r] 已经有序。 上文中提到的 「划分」 过程是：从子数组 a[l⋯r] 中选择任意一个元素 x 作为主元，调整子数组的元素使得左边的元素都小于等于它，右边的元素都大于等于它， x 的最终位置就是 q。

解题思路

在分解的过程当中，我们会对子数组进行划分， 如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]； 否则，如果 q比目标下标小，就递归右子区间，否则递归左子区间。 这样就可以把原来递归两个区间变成只递归一个区间， 提高了时间效率。这就是「快速选择」算法。 解释：快速排序是先选择一个中枢（一般我们选第一个）， 然后遍历后面的元素，最终会把数组分为两部分，前面部分比中枢值小， 后面部分大于或等于中枢值，如果交换之后中枢值所在的位置就是从后面数第k个， 我们直接返回中枢值即可，如果从后面数大于第k个， 我们只需按照同样的方式从后面部分开始找即可。如果从后面数小于第k个，我们同样从前面部分开始查找，

public class KthLargestElementinanArray215 { Random random = new Random(); public int findKthLargest(int[] nums, int k) { return quickSelect(nums, 0, nums.length - 1, nums.length - k); } public int quickSelect(int[] a, int l, int r, int index) { int q = randomPartition(a, l, r);//在[l,r]经过排序之后得到想要索引的值 if (q == index) { return a[q];//q与要求的index祥等则返回 } else { return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index); } } public int randomPartition(int[] a, int l, int r) {//主要是负责随机产生一个数i，然后 int i = random.nextInt(r - l + 1) + l;//该方法的作用是生成一个随机的int值，该值介于[l,r+1)相当于[l,r]的区间 swap(a, i, r);//索引的值与r交换 return partition(a, l, r); } public int partition(int[] a, int l, int r) { int x = a[r], i = l - 1; for (int j = l; j < r; ++j) { if (a[j] <= x) { swap(a, ++i, j); } } swap(a, i + 1, r);//i相当于正在指向的元素，这一步我不明白 return i + 1; } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }

347、给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

桶排序法：

第一种，以出现的频率为下标

public List<Integer> topKFrequent(int[] nums, int k){ Map<Integer,Integer> frequencyForNum = new HashMap<>(); for(int num : nums){ frequencyForNum.put(num,frequencyForNum.getOrDefault(num,0)+1); } List<Integer>[] buckets = new ArrayList[nums.length+1]; for(int key : frequencyForNum.keySet()){ int frequency = frequencyForNum.keySet(key); if(buckets[frequency]==null){ buckets[frequency] == new ArrayList<>(); } buckets[frequency].add(key); } List<Integer> topK = ArrayList<>(); for(int i =buckets.length-1;i>=0 && topK.size()<k;i--){ if(buckets[i]==null){ continue; } if(buckets[i].size()<=(k-topK.size())){ topK.addAll(buckets[i]); }else{ topK.addAll(buckets[i].subList(0,k-topK.size())); } } return topK； }

总结：第一个方法比较难理解

第一种，以出现的频率为下标

//思路：首先依旧使用哈希表统计频率，统计完成后， //创建一个数组，将频率作为数组下标， //对于出现频率不同的数字集合，存入对应的数组下标即可。 public List<Integer> topKFrequent2(int[] nums, int k) { List<Integer> res = new ArrayList(); // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值 HashMap<Integer,Integer> map = new HashMap(); for(int num : nums){ if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } //桶排序 //将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标 List<Integer>[] list = new List[nums.length+1]; for(int key : map.keySet()){ // 获取出现的次数作为下标 int i = map.get(key); if(list[i] == null){ list[i] = new ArrayList(); } list[i].add(key); } // 倒序遍历数组获取出现顺序从大到小的排列 for(int i = list.length - 1;i >= 0 && res.size() < k;i--){ if(list[i] == null) continue; res.addAll(list[i]); } return res; } }