大家好，我是拿输出博客督促自己刷题的老三，前面学习了十大排序：万字长文|十大基本排序，一次搞定！，接下来我们看看力扣上有没有什么能拿排序解决的题目吧！
排序基础
简单了解一下基本的排序——
基本排序分类：
基本排序性能：
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(n^(1.3-2)) | O(n²) | O(n) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(n²) | O(nlogn) | O(nlogn) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n) | 稳定 |
| 桶排序 | O(n+k) | O(n²) | O(n) | O(n+k) | 稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
更具体的可以查看：万字长文|十大基本排序，一次搞定！
好了，开始我们愉快的刷题之旅吧！
刷题现场
LeetCode912. 排序数组
☕ 题目：912. 排序数组 (https://leetcode-cn.com/problems/sort-an-array/)
❓ 难度：中等
📕 描述：给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
💡 思路：
这道题如果用api，一行就搞定了——Arrays.sort(nums)，那面试官的反应多半是，门在那边，慢走不送。
所以，毫无疑问，我们要手撕排序了。
如果对排序算法不太熟，可以上一个冒泡排序，但是这个明显只能说中规中矩，所以，我们选择：
手撕快排
关于快排，就不多讲。
直接上代码：
class Solution { public int[] sortArray(int[] nums) { quickSort(nums,0,nums.length-1); return nums; } public void quickSort(int[] nums,int left, int right){ //结束条件 if(left>=right){ return; } //分区 int partitionIndex=partition(nums,left,right); //递归左分区 quickSort(nums,left,partitionIndex-1); //递归右分区 quickSort(nums,partitionIndex+1,right); } public int partition(int[] nums,int left,int right){ //基准值 int pivot=nums[left]; //mark标记下标 int mark=left; for(int i=left+1;i<=right;i++){ if(nums[i]<pivot){ //小于基准值，则mark后移，并交换位置 mark++; int temp=nums[mark]; nums[mark]=nums[i]; nums[i]=temp; } } //把基准值放到mark的位置 nums[left]=nums[mark]; nums[mark]=pivot; return mark; } }
- 🚗 时间复杂度：快排时间复杂度O(nlogn)
有时间的可以把十大排序都在这道题练上一练。
LeetCode347. 前 K 个高频元素
☕ 题目：347. 前 K 个高频元素(https://leetcode-cn.com/problems/top-k-frequent-elements/)
❓ 难度：中等
📕 描述：
给你一个整数数组 nums，请你将该数组升序排列。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
提示：
1 <= nums.length <= 105 k 的取值范围是 [1, 数组中不相同的元素的个数] 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
**进阶：**你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
💡 思路：
这道题第一思路是什么呢？
统计元素出现频率，从大到小排序，取前k个元素。
我们想挑战一下进阶要求，时间复杂度优于O(nlogn)，所以熟悉的冒泡、快排之类的比较类排序都不可用，只能使用非比较类的三种排序方法：计数排序、桶排序、基数排序。
这里我们选择HashMap+桶排序的方式。
使用HashMap存储元素出现频率，使用桶排序来进行排序。
代码如下：
public int[] topKFrequent(int[] nums, int k) { //使用HashMap存储元素出现频率 Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); } //桶 List<Integer>[] buckets = new List[nums.length + 1]; //往桶里添加元素出现次数 for (Integer key : map.keySet()) { //根据出现频率决定元素入哪个桶 int count = map.get(key); //初始化桶 if (buckets[count] == null) buckets[count] = new ArrayList<>(); //将元素存到桶中 buckets[count].add(key); } //结果列表 List<Integer> result = new ArrayList<>(); //取倒数k个非空桶中的元素 for (int i = buckets.length - 1; k > 0; i--) { if (buckets[i] != null) { //取出桶中的元素 for (Integer num : buckets[i]) { result.add(num); k--; } } } //将列表中的元素赋给数组 int[] res = new int[result.size()]; for (int i = 0; i < res.length; i++) { res[i] = result.get(i); } return res; }
- 🚗 时间复杂度：这道题用了桶排序，时间复杂度O(n)。
剑指 Offer 45. 把数组排成最小的数
☕ 题目：剑指 Offer 45. 把数组排成最小的数 (https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/)
❓ 难度：中等
📕 描述：
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2] 输出: "102"
示例 2:
输入: [3,30,34,5,9] 输出: "3033459"
💡 思路：
稍微分析一下这道题，发现这道题其实也是一道排序题。
只要我们把数组里的元素按照某种规则进行排序。
现在的问题就是这个排序规则是什么呢？
因为需要拼接字符串，以[3，30]为例，“3”+“30”=“330”，“30”+“3”=“303”，330>303，那么我们就可以说3大于30。
所以定义规则：
- 若拼接字符串 x+y>y+x ，则 x
大于y ； - 反之，若拼接字符串 x+y<y+x ，则 x
小于y ；
规则图如下（来源参考[2）：
那么，这道题我们就知道怎么写了。
用我们自定义的排序规则从小到大排序数组。
排序方法我们选择快排，所以这道题就是自定义排序+快排。
代码如下：
public String minNumber(int[] nums) { quickSort(nums, 0, nums.length - 1); //结果 StringBuilder sb = new StringBuilder(); for (int num : nums) { sb.append(String.valueOf(num)); } return sb.toString(); } //快排 public void quickSort(int[] nums, int left, int right) { if (left >= right) return; int partionIndex = partion(nums, left, right); quickSort(nums, left, partionIndex - 1); quickSort(nums, partionIndex + 1, right); } public int partion(int[] nums, int left, int right) { int pivot = nums[left]; int mark = left; for (int i = left + 1; i <= right; i++) { if (lessThan(nums[i], pivot)) { mark++; int temp = nums[mark]; nums[mark] = nums[i]; nums[i] = temp; } } nums[left] = nums[mark]; nums[mark] = pivot; return mark; } //自定义大小比较规则 public boolean lessThan(int x, int y) { String sx = String.valueOf(x), sy = String.valueOf(y); return (sx + sy).compareTo(sy + sx) < 0; }
写的比较臃肿，但比较清晰。
有一种利用内置排序来实现的写法，不太建议：
public String minNumber(int[] nums) { String[] strs = new String[nums.length]; for(int i = 0; i < nums.length; i++){ strs[i] = String.valueOf(nums[i]); } Arrays.sort(strs, (x,y) -> (x+y).compareTo(y+x)); StringBuilder ans = new StringBuilder(); for(String s : strs) ans.append(s); return ans.toString(); }
- 🚗 时间复杂度：O(nlogn)。
有一道题：179. 最大数 和这道题基本一样。
剑指 Offer 51. 数组中的逆序对
☕ 题目：剑指 Offer 51. 数组中的逆序对 (https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)
❓ 难度：困难
📕 描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4] 输出: 5
💡思路：
这一道题是困难，有没有被吓住？
其实这道题如果用归并排序的思路去解决的话，就没有想象中的那么难。
归并排序这里就不讲了。
解决这道题，我们只需要在归并排序的基础上，加上对逆序对的统计：
归并+逆序对统计示意图（图片来源参考[3]）：
现在的关键点是，归并的过程如何计算逆序对个数？
我们可以看一下，合并的时候，l指向左子数组2的位置，r指向右子数组0的位置，num[l]>nums[r]，因为子数组是有序的，所以l后面几个元素也都一定大于0，所以可以得出，此时逆序对数量=mid-l+1。
代码如下：
class Solution { //统计逆序对 int count = 0; public int reversePairs(int[] nums) { mergeSort(nums, 0, nums.length - 1); return count; } //归并排序 public void mergeSort(int[] nums, int left, int right) { //结束 if (left >= right) return; int mid = left + (right - left) / 2; //左半部分 mergeSort(nums, left, mid); //右半部分 mergeSort(nums, mid + 1, right); //合并 merge(nums, left, mid, right); } //合并 public void merge(int[] arr, int left, int mid, int right) { //临时数组 int[] tempArr = new int[right - left + 1]; //指向左右子数组指针 int l = left, r = mid + 1; int index = 0; //把左右子数组较小元素放入到临时数组 while (l <= mid && r <= right) { if (arr[l] <= arr[r]) { tempArr[index++] = arr[l++]; } else { //增加一行，统计逆序对 count += (mid - l + 1); tempArr[index++] = arr[r++]; } } //将左子数组剩余的元素拷贝到临时数组 while (l <= mid) { tempArr[index++] = arr[l++]; } //将右边子数组剩余的元素拷贝到临时数组 while (r <= right) { tempArr[index++] = arr[r++]; } //将临时数组的元素拷贝给原数组 for (int i = 0; i < tempArr.length; i++) { arr[i + left] = tempArr[i]; } } }
- 🚗 时间复杂度：归并排序时间复杂度O(nlogn)。
LeetCode147. 对链表进行插入排序
☕ 题目：剑指 Offer 51. 数组中的逆序对 (https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)
❓ 难度：困难
📕 描述：
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3 输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0 输出: -1->0->3->4->5
💡 思路：
这道题不只是插入排序，还涉及到链表的操作，关于链表，可以查看：LeetCode通关：听说链表是门槛，这就抬脚跨门而入
- 关于插入排序：我们需要从未排序序列里将元素插入到排序序列的合适位置
- 关于链表插入：链表插入是插入节点前驱节点改变后继的一个操作，为了头插也能统一，通常我们会加一个虚拟头节点
- 所以，综合起来，我们需要标记有序序列和无序序列的分界点，遍历无序序列的时候，记录前驱，当需要将无序序列插入到有序序列的时候，遍历有序序列，找到插入位置，先删除该节点，再插入
代码如下：
public ListNode insertionSortList(ListNode head) { if (head == null && head.next == null) { return head; } //虚拟头节点 ListNode dummy = new ListNode(-1); dummy.next = head; //记录有序序列终点 ListNode last = head; //遍历无序序列 ListNode after = head.next; while (after != null) { if (last.val <= after.val) { after = after.next; last = last.next; continue; } //遍历有序序列，查找插入位置 ListNode prev = dummy; while (prev.next.val <= after.val) { prev = prev.next; } //找到插入位置 //删除无序序列节点 last.next = after.next; //插入有序序列 after.next = prev.next; prev.next = after; //继续移动 after=last.next; } return dummy.next; }
- 🚗 时间复杂度：O(n²)。
总结
熟悉的顺口溜总结：
简单的事情重复做，重复的事情认真做，认真的事情有创造性地做。
我是三分恶，一个追求实力，正在努力的程序员。
点赞、关注不迷路，咱们下期见！
