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;
}
}

最后

以上就是纯情纸飞机为你收集整理的LeetCode刷题笔记（3）LeetCode刷题笔记（3）背景215、在未排序的数组中找到第 k 个最大的元素。347、给定一个非空的整数数组，返回其中出现频率前 k 高的元素。的全部内容，希望文章能够帮你解决LeetCode刷题笔记（3）LeetCode刷题笔记（3）背景215、在未排序的数组中找到第 k 个最大的元素。347、给定一个非空的整数数组，返回其中出现频率前 k 高的元素。所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。