devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode——排序（215.数组中的第K个最大元素、347.出现频率最多的 k 个元素、451. 根据字符出现频率排序、75. 颜色分类）快排、桶排序_leetcode 215

作者：凡人多烦事01 | 2024-02-09 19:36:15

赞

踩

leetcode 215

一、215. 数组中的第K个最大元素

1.1  题目叙述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。（难度中等）

示例 1:输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

1.2 代码

1.2.1暴力+API

  1. package Sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * @author : lkw
  7.  * @data : 2021/3/11 10:32
  8.  * @description :215. 数组中的第K个最大元素(难度中等)
  9.  * 方法一：暴力解法
  10.  * 时间复杂度:O(nlogn)，此解法时间消耗为排序，jdk默认的是快速排序，
  11.  * 空间复杂度：O(1)，使用的是原地排序
  12.  *
  13.  **/
  14. public class findKthLargest_01 {
  15.     public int findKthLargest(int[] nums, int k) {
  16.         Arrays.sort(nums);
  17.         return nums[nums.length-k];
  18.         //若有5个元素，第二大，就是nums[5-2]
  19.         //若有5个元素，第四大就是nums[5-4],即nums[nums.length-k]
  20.  
  21.     }
  22. }

1.2.2 快排（不推荐使用）

  1. package Sort;
  2.  
  3. /**
  4.  * @author : lkw
  5.  * @data : 2021/3/11 11:54
  6.  * @description :215. 数组中的第K个最大元素(难度中等)
  7.  * 方法二：快速排序
  8.  **/
  9. /*在程序运行开始前就知道数组的元素（所有的元素都是机前确定，并且不变），可以使用快速选择排序，
  10. // 若是动态数据流的情况，则只能使用堆排序
  11.     //快速选择：即快排中轴值计算的过程，小于轴值的放在左侧，大于的放于右侧
  12.     一轮排序后，通过排序后轴值下标与k之间的关系，选定轴值左侧或右侧，进行下一步操作
  14.   **/
  15. public class findKthLargest_02 {
  16.     public static void main(String[] args) {
  17.         int[] nums = {23,46,20,8,11,18};
  18.         System.out.println(findKthLargest(nums, 2));
  19.  
  20.     }
  21.     public static int findKthLargest(int[] nums, int k){
  22.         int left= 0;
  23.         int right= nums.length-1;
  24.         int target = nums.length-k;
  25.         while (true){
  26.             int index = partition(nums,left,right);
  27.  
  28.             if (index==target){
  29.                 return nums[index];
  30.             }
  31.             else if(index<target){
  32.                 left=index+1;
  33.             }
  34.             else  right=index-1;
  35.         }
  36.  
  37.  
  38.     }
  39.  
  40.     public static int partition(int[] nums,int left,int right){
  41.         int pivot = nums[left];
  42.         int j=left;
  43.         for (int i = left+1; i <= right; i++) {
  44.             if (nums[i]<pivot){
  45.                 j++;
  46.                 swap(nums,i,j);
  47.             }
  48.         }
  49.         swap(nums,j,left);
  50.     return j;
  51.  
  52.     }
  53.     public static void swap(int[] nums,int i,int j){
  54.         int temp = nums[i];
  55.         nums[i]= nums[j];
  56.         nums[j] = temp;
  57.     }
  58. }

1.2.3 优先队列(容量为len，易理解)

补充知识：Lambda表达式

Lambda表达式：接受2个参数(数字),并返回他们的差值 (x, y) -> x – y

Java Lambda 表达式：Java Lambda 表达式 | 菜鸟教程

小顶堆:每个结点的值都小于或等于其左右孩子结点的值

小顶堆的比较器：(a, b) -> a - b

大顶堆的比较器：(a, b) -> b - a

  • poll：将首个元素从队列中弹出，如果队列是空的，就返回null
  • peek：查看首个元素，不会移除首个元素，如果队列是空的就返回null

思路：创建一个为len的小顶堆，输出len-k个最小元素后，堆中剩余k个最大元素，则堆顶是则是第k大元素。

小顶堆:每个结点的值都小于或等于其左右孩子结点的值

  1. package Sort;
  2.  
  3. /**
  4.  * @author : lkw
  5.  * @data : 2021/3/11 12:14
  6.  * @description :优先队列（1）
  7.  **/
  8.  
  9. import java.util.PriorityQueue;
  10. import java.util.Random;
  11.  
  12. /**
  13.  * 创建一个为len的小顶堆，输出len-k个元素后，堆中剩余k个最大元素，则堆顶是则是第k大元素
  14.  */
  15. public class findKthLargest_03 {
  16.     public static void main(String[] args) {
  17.         int[] nums = {23,20,0,8,11,18};
  18.         System.out.println(findKthLargest(nums, 2));
  19.     }
  20.  
  21.  
  22.  
  23.     public static int findKthLargest(int[] nums, int k) {
  24.         int len = nums.length;
  25.         PriorityQueue<Integer> priorityQueue= new PriorityQueue<>(len,(a,b)->(a-b));
  26.         for (int i = 0; i <len ; i++) {
  27.             priorityQueue.add(nums[i]);
  28.  
  29.         }
  30.         for (int i = 0; i < len-k; i++) {
  31.          priorityQueue.poll();
  32.         }
  33.         return priorityQueue.peek();
  34.     }
  35. }
  36.  
  37.

1.2.4 优先队列 (容量为k+1)

若我们创建一个k+1的小顶堆，先放入k个元素

再将待插入的元素放入小顶堆，此时弹出一个堆顶元素，一直保持堆内还是k个最小元素，程序最后的栈顶就是最k大元素。

可以参考：力扣 

  1. package Sort;
  2.  
  3. import java.util.PriorityQueue;
  4.  
  5. /**
  6.  * @author : lkw
  7.  * @data : 2021/3/12 10:11
  8.  * @description :
  9.  **/
  10. public class findKthLargest_03 {
  11.     public static void main(String[] args) {
  12.         //int[] nums = {23,46,20,8,11,18};
  13.         int[] nums = {3,2,1,5,6,4};
  14.         System.out.println(findKthLargest(nums, 2));
  15.  
  16.     }
  17.     public static int findKthLargest(int[] nums, int k) {
  18. /*优先队列思想：数组长度为len，输出第k大元素，即数组排序后[0...len-k-1][len-k...len-1],后半段k个元素中最小的元素
  19.  后半段k个元素中最小的元素，可以创建一个容量为k的小顶堆，最后输出堆顶元素。
  20.  但是现在数组时乱序：我们可以创建一个k的小顶堆，始终保持有k个
  21.  则先放入k个元素，堆满之后若此时元素若大于堆顶则先弹出在放入
  23. 若我们创建一个k+1的小顶堆，先放入k个元素
  24. 再将待插入的元素放入小顶堆，此时弹出一个堆顶元素，此时堆内还是k个最小元素
  25.          */
  26.         PriorityQueue<Integer> priorityQueue= new PriorityQueue<>(k+1,(a,b)->(a-b));
  27.         //先放入k个元素
  28.         for (int i = 0; i < k; i++) {
  29.             priorityQueue.add(nums[i]);
  30.  
  31.         }
  32.         for (int i = k; i < nums.length; i++) {
  33.             priorityQueue.add(nums[i]);
  34.             priorityQueue.poll();
  35.  
  36.         }
  37.         return priorityQueue.peek();
  38.  
  39.     }
  40. }

  1. //大顶堆
  2. public static int findKthLargest(int[] nums, int k) {
  3.         int len = nums.length;
  4.         PriorityQueue<Integer>  priorityQueue= new PriorityQueue<>(len,(a,b)->(b-a));//大顶堆
  5.         for (int i = 0; i < len; i++) {
  6.             priorityQueue.add(nums[i]);
  7.         }
  8.         for (int i = 0; i < k-1; i++) {
  9.             priorityQueue.poll();
  10.         }
  11.         return priorityQueue.peek();
  12.     }

以下为桶排序的三个题

二、347.出现频率最多的 k 个元素

2.1 题目描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。（难度中等）

示例 1:输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:输入: nums = [1], k = 1
输出: [1]

提示：你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

补充：理解List集合add()和addAll()的区别可参考博文：

简单易懂List集合add()和addAll()的区别_IX的博客-CSDN博客

Map.get() 方法返回指定键所映射的值 。

Map.ketSet() 方法将获取 Map 集合的所有键名。

Add方法是将传入的参数作为当前List中的一个item存储，即使你传入一个List也只会令当前的List增加1个元素 。

AddAll是传入一个List，将此List中的所有元素加入到当前List中，也就是当前List会增加的元素个数为传入的List的大小。 

2.2 代码 

2.2.1 桶排序

具体题解力扣

  • 借助 哈希表 来建立数字和其出现频率的映射，遍历一遍数组统计元素的频率。
  • 频率统计结束后，设置若干个桶，每个桶放出现频率相同的值，即第i个桶，存储出现频率为i的数。
  • 倒序遍历数组获取出现顺序从大到小的排列

补充：关于Map的博文：Map 综述（一）：彻头彻尾理解 HashMap_Rico's Blogs-CSDN博客_hashmap　

Map 是 Key-Value 对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。HashMap 是 Java Collection Framework 的重要成员，也是Map族(如下图所示)中我们最为常用的一种。简单地说，HashMap 是基于哈希表的 Map 接口的实现，以 Key-Value 的形式存在，即存储的对象是 Entry (同时包含了 Key 和 Value) 。

同样地，HashSet 也是 Java Collection Framework 的重要成员，是 Set 接口的常用实现类，但其与 HashMap 有很多相似之处。对于 HashSet 而言，其采用 Hash 算法决定元素在Set中的存储位置，这样可以保证元素的快速存取；

HashMap首先会调用Key的hashCode方法，然后基于此获取Key哈希码，通过哈希码快速找到某个桶，这个位置可以被称之为 bucketIndex。如果两个对象的hashCode不同，那么equals一定为 false；否则，如果其hashCode相同，equals也不一定为 true。所以，理论上，hashCode 可能存在碰撞的情况。

hashCode ： Object 的 native方法 , 获取对象的哈希值，用于确定该对象在哈希表中的索引位置，它实际上是一个int型整数。 

List、ArrayList和LinkedList

  • ArrayList是Array(动态数组)的数据结构，LinkedList是Link(链表)的数据结构。
  • List是一个接口，而ArrayList是List的实现类。因此List不能作为定义一个实例对象，只能作为引用。

当数列范围太大，或者不是整数时，我们可以使用桶排序，类似于计数排序。

所有的桶保存在ArrayList集合当中，每一个桶被定义成一个ArrayList。

桶排序的博文：漫画：什么是桶排序？_程序人生的博客-CSDN博客 

for (int num:nums)中的num为nums中元素的值。

String reverse = new StringBuffer(a).reverse().toString();   //翻转字符a

  1. package Sort;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.HashMap;
  5. import java.util.List;
  6.  
  7. /**
  8.  * @author : lkw
  9.  * @data : 2021/3/15 9:06
  10.  * @description :347. 前 K 个高频元素
  11.  **/
  12. public class topKFrequent_01 {
  13.     //思路一：拿一个数组n[k+1]记录0-k的次数，然后比较数组n[k+1]的大小
  14.  
  15.     /*
  16.     Map.get() 方法返回指定键所映射的值
  17.     Map.keySet() 方法将获取 Map 集合的所有键名
  18.     Add方法是将传入的参数作为当前List中的一个item存储，即使你传入一个List也只会令当前的List增加1个元素
  19.     AddAll是传入一个List，将此List中的所有元素加入到当前List中，也就是当前List会增加的元素个数为传入的List的大小
  21.      */
  22. //1.先统计频率
  23.     public static void main(String[] args) {
  24.         int[] nums = {1,1,1,2,2,3};
  25.         System.out.println(topKFrequent(nums, 2));
  26.  
  27.  
  28.     }
  29.     public static int[] topKFrequent(int[] nums, int k) {
  30.         List<Integer> reslist = new ArrayList();
  31.         //使用map存入的是键值对，统计每个元素出现的频率，元素为键，频率为值
  32.         HashMap<Integer,Integer> map = new HashMap();
  33.         for (int num:nums){
  34.             if (map.containsKey(num)) {
  35.                 map.put((Integer)num,map.get(num) + 1);
  36.             }
  37.             else
  38.                 map.put((Integer)num,1);
  39.             }
  40.     //桶排序，频率作为数组下标，对于出现频率不同的元素，存入对于的数组下标
  41.         //有n+1个桶，因为元素出现的频率可能有0次，1次，2次.....n次 , 一共有n+1种可能
  42.         //
  43.         List<Integer>[] list = new List[nums.length+1];//创建了一个元素都为List型的数组
  44.         for (int key: map.keySet()){
  45.             //i为出现的频率
  46.             int i = map.get(key);
  47.             if (list[i]==null){
  48.                 //防止空指针，防止i第一次进来的时候报错
  49.                 //因为频率相同也可放入，因为array[i]也是一个数组列表
  50.                 list[i]=new ArrayList<>();
  51.             }
  52.             //创建好数组列表后，再将数值放入
  53.             list[i].add((Integer)key);//注意：这里不是else
  54.         }
  55. //倒序遍历数组，获得频率由大到小的次序
  56.         for (int i = list.length-1;i>=0 && reslist.size()<k;i--){
  57.             if (list[i]==null) continue;
  58.             reslist.addAll(list[i]);//为啥不是else？
  59.         }
  60.         System.out.println(reslist);
  61.             int[] resArray = new int[reslist.size()];
  62.        // int[] res = new int[k];
  63.         for (int i = 0; i < k; i++) {
  64.             resArray[i] = reslist.get(i);
  65.         }
  66.  
  67.         return resArray;
  68.  
  69.     }
  70.  
  71. }

 时间复杂度：遍历数组，统计频率的时复为O(n),桶排序的时复为O(n+1)，list转数组时复为O(n),因此最后的时间复杂度为O(n).

空间复杂度：O(n)， map,list,relist,reArray所占用的内存。

三、451. 根据字符出现频率排序

3.1 题目描述

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。（中等难度）

示例 1:

输入:"tree"

输出:"eert"

解释:  'e'出现两次，'r'和't'都只出现一次。

因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

3.2 代码

3.2.1 桶排序

此题和上一题347题为一个思路

先统计频率，在桶排序，在组合字符串。

  1. package Sort;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.HashMap;
  5.  
  6. /**
  7.  * @author : lkw
  8.  * @data : 2021/3/21 17:20
  9.  * @description :451. 根据字符出现频率排序(中等)
  10.  **/
  11. public class frequencySort_01 {
  12.     public static void main(String[] args) {
  13.         String s = "cccaaaabcdw";
  14.         frequencySort(s);
  15.     }
  16.     public static String frequencySort(String s) {
  17.         char array[] = s.toCharArray();
  18.         //键为：char，值为频率
  19.         HashMap<Character, Integer> map = new HashMap();
  20.         for (int i = 0; i < array.length; i++) {
  21.             char key = array[i];
  22.             if (map.containsKey(key)) {
  23.                 map.put(key, map.get(key) + 1);
  24.             } else
  25.                 map.put(key, 1);
  26.         }
  27.  
  28.         //System.out.println(map);//{r=1, t=1, e=2}
  29.  
  30.         //创建桶
  31.         //有n+1个桶，因为元素出现的频率可能有0次，1次，2次.....n次 , 一共有n+1种可能
  32.         //第i个桶存出现频率为i的字符
  33.         ArrayList<Character>[] list = new ArrayList[array.length + 1];
  34.         for (char key : map.keySet()) {
  35.             int index = map.get(key);
  36.             if (list[index] == null) {
  37.                 list[index] = new ArrayList();
  38.             }
  39.             list[index].add(key);
  40.         }
  41.         System.out.println(list[3]);
  42.  
  43.         //组合字符
  44.         //建议使用StringBuilder,执行效率高
  45. //        String a = "";
  46.         //倒序扫描桶，因为频率高的在最后面
  47.         StringBuilder res = new StringBuilder();
  48.         for (int i=list.length-1;i>=0;i--) {
  49.             if (list[i] != null) {
  50.                 for (char ch:list[i]){
  51.                     for (int j = 0; j < i; j++) {
  52.                         //a=a+ch;
  53.                         res.append(ch);
  54.                     }
  55.                 }
  56.             }
  57.  
  58.         }
  59.  
  60.         //System.out.println(a);
  61.         //return a;
  62.         System.out.println(res.toString());
  63.        return res.toString();
  64.     }
  65.  
  66. }
  67.  
  68.

时间复杂度：O(n).   统计频率需要 O(n)；创建桶遍历 HashMap 需要 O(n)；遍历桶的集合需要 O(n) *两个常数，依然是 O(n)。

空间复杂度：O(n).   建立 HashMap 需要 O(n)；建立 n+1个桶需要 O(n)。

最后组合字符串用的string：

最后输出组合字符串用的StringBuilder：

补充：StringBuffer和StringBuilder的运行效率和内存占用几乎一致，这是因为二者都是对对象本身进行操作，不会生成新的字符串对象。二者的区别主要是StringBuffer是线程安全的，而StringBuilder是线程不安全的。

String是不可变的对象，每次对String进行操作的时候，都会生成一个新的对象，这会对系统的性能造成影响。

执行效率竟然如此之大，因此以后建议使用StringBuilder。 

四、75. 颜色分类

4.1 题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。（难度中等）

示例 1：输入：nums = [2,0,2,1,1,0]
              输出：[0,0,1,1,2,2]

示例 2：输入：nums = [2,0,1]
              输出：[0,1,2]

示例 3：输入：nums = [0]
              输出：[0]

示例 4：输入：nums = [1]
              输出：[1]

4.2 代码

4.2.1 桶排序

  1. package Sort;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.HashMap;
  6.  
  7. /**
  8.  * @author : lkw
  9.  * @data : 2021/3/21 20:36
  10.  * @description :75. 颜色分类
  11.  * 桶排序
  12.  **/
  13. public class sortColors_01 {
  14.     public static void main(String[] args) {
  15.         int nums[] = {1,1,0,2,0,1,2,2,2};
  16.         sortColors(nums);
  17.     }
  18.  
  19.     public static void sortColors(int[] nums) {
  20.         //统计频率，hashmap，key：数值，value：频率
  21.         HashMap<Integer,Integer> map = new HashMap();
  22.         for (int num:nums){
  23.             if (map.containsKey(num)){
  24.                 map.put(num,map.get(num)+1);
  25.             }
  26.             else
  27.                 map.put(num,1);
  28.  
  29.         }
  30.         //System.out.println(map);
  31.         
  32.         
  33.         int t=0;
  34.         for (int key: map.keySet()){
  35.             for (int i =0;i<map.get(key);i++){
  36.                 nums[t++]=key;
  37.             }
  38.         }
  39.         //System.out.println(Arrays.toString(nums));
  40.  
  41.     }
  42. }

时间复杂度：O(n), 遍历数组nums时构造HashMap为O(n),最后构建nums，遍历map用时O(n),因此为O(n)。

空间复杂度：O(n),  map的大小为O(n)

 

4.2.2 数组+指针

此代码中： 0 的优先级> 1 的优先级 >2 的优先级

即时2先被填入，但是若最后值不为2，会被覆盖掉。

  1. package Sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * @author : lkw
  7.  * @data : 2021/3/21 21:28
  8.  * @description :数组
  9.  **/
  10. public class sortColors_02 {
  11.     public static void main(String[] args) {
  12.         int nums[] = {1, 1, 0, 2, 0, 1, 2, 2, 2};
  13.         sortColors(nums);
  14.     }
  15.  
  16.     public static void sortColors(int[] nums) {
  17.         //zero表示数字0的右侧边界，one、two分别表示1 和 2 的右侧边界
  18.         int zero = 0;
  19.         int one = 0;
  20.         int two = 0;
  21.  
  22.  
  23.         int length = nums.length;
  24.  
  25.         for(int i = 0; i < length; i++)
  26.         {
  27.             //记录下待处理的值
  28.             int temp = nums[i];
  29.  
  30.             //不管怎样，我先给你填个2
  31.             nums[two] = 2;
  32.             two ++;
  33.  
  34.             // <=1的话 1的右侧边界one要向右挪一格
  35.             if(temp <= 1)
  36.             {
  37.                 nums[one] = 1;
  38.                 one ++;
  39.             }
  40.  
  41.             //为0的话 0的右侧边界zero要向右挪一格
  42.             if(temp == 0)
  43.             {
  44.                 nums[zero] = 0;
  45.                 zero ++;
  46.             }
  47.         }
  48.         //System.out.println(Arrays.toString(nums));
  49.     }
  50. }

时间复杂度：O(n)

空间复杂度： O(1)

化简以上代码：

  1. package Sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * @author : lkw
  7.  * @data : 2021/3/22 9:21
  8.  * @description :
  9.  **/
  10. public class sortColors_03 {
  11.     public static void main(String[] args) {
  12.         int nums[] = {1, 1, 0, 2, 0, 1, 2, 2, 2};
  13.         sortColors(nums);
  14.     }
  15.  
  16.     public static void sortColors(int[] nums) {
  17.         int zeao=0,one=0;
  18.         for (int i=0;i< nums.length;i++){
  19.             int tem=nums[i];
  20.             nums[i]=2;
  21.  
  22.             if (tem<=1){
  23.                 nums[one++]=1;
  24.             }
  25.             if (tem==0){
  26.                 nums[zeao++]=0;
  27.             }
  28.  
  29.         }
  30.         //System.out.println(Arrays.toString(nums));
  31.  
  32.     }
  33.  
  34. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/72818?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号