①归并排序、快速排序 、堆排序、计数排序
🚀归并排序
⚪步骤
归并排序：
归并排序是一种分治法（Divide and Conquer）的经典排序算法，它的基本思想是将原始数组划分成较小的数组，然后递归地对这些小数组进行排序，最后再将排好序的小数组合并成一个整体有序的数组。下面是**归并排序的详细过程： **
详细步骤：
分解（Divide）:
- 将数组一分为二，找到中间位置。
- 递归地对左右两个子数组进行分解，直到每个子数组只有一个元素。
排序（Conquer）：
- 当每个子数组只包含一个元素时，认为它已经有序。
合并（Merge）：
- 将两个有序的子数组合并成一个有序的数组。
- 创建一个临时数组，依次比较两个子数组的元素，将较小的元素放入临时数组。
- 如果其中一个子数组的元素已经全部放入临时数组，将另一个子数组的剩余部分直接放入临时数组。
- 将临时数组复制回原始数组的相应位置，完成合并。
⚪实现
算法实现：
public class mergeSortTest { //main函数，用于测试 public static void main(String[] args) { //手动创建数组 int[] arr = new int[] {1,5,88,3,-8,7,256,-8,6,15,-96}; //使用归并排序 process(0,arr.length-1,arr); //遍历排序后数组 for(int i = 0;i < arr.length;++i) { System.out.print(arr[i] + " "); } } //分解 + 合并（分解合并过程中已完成排序）： public static void process(int L, int R, int[] arr) { if(L == R) return; //下标重合，结束 int mid = L + ((R - L) >> 1); //获取中间下标mid、 (R - L) >> 1 等同于 (R - L) / 2 process(L , mid, arr); //分解左子数组 process(mid + 1, R, arr); //分解右子数组 merge(L, mid, R, arr); //合并 } //合并： public static void merge(int L, int mid, int R, int[] arr) { int[] help = new int[R - L + 1]; //帮组数组 int p1 = L; //左子数组起始下标 int p2 = mid + 1; //右子数组起始下标 int i = 0; //帮组数组起始下标 //合并，两个子数组元素按顺序比较，较小的元素放入帮组数组，重复此步骤。 while(p1 <= mid && p2 <= R) { help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } while(p1 <= mid) { help[i++] = arr[p1++]; } while(p2 <= R) { help[i++] = arr[p2++]; } //将帮助数组的元素赋值回元素组。 for(i = 0;i < help.length; ++i) { arr[i + L] = help[i]; } } }
⚪复杂度
复杂度分析：
- 时间复杂度： O(n log n) - 归并排序始终都是O(n log n)的，无论最坏情况还是平均情况。
- 空间复杂度： O(n) - 归并排序需要一个与原始数组同样大小的辅助数组来进行合并操作，因此空间复杂度为O(n)。
🚀快速排序
⚪步骤
快速排序：
快速排序（Quick Sort）是一种常用的基于分治思想的排序算法。它的基本思想是通过一趟排序将待排序的记录分割成独立的两部分，其中一部分的所有记录均比另一部分的记录小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。快速排序的核心是选择一个基准元素，将小于等于基准的元素放在左边，大于基准的元素放在右边，然后对左右两个子序列分别递归地应用相同的方法。
详细步骤：
- 选择基准元素：
- 从待排序数组中选择一个元素作为基准元素。通常选择第一个元素、最后一个元素或者中间元素。（本文等概率随机选取一个元素作为基准，避免最坏复杂度的发生）
- 分区（Partition）：
- 将数组中小于等于基准的元素放在基准的左边，大于基准的元素放在右边。这一步通常称为分区操作。
- 使用两个指针，一个在数组的起始位置，一个在数组的结束位置，分别向中间移动，交换不符合条件的元素，直到两个指针相遇。
- 递归排序：
- 对基准左右两侧的子数组进行递归排序。重复以上步骤，直到每个子数组的大小为1或0。
⚪实现
算法实现：
public class Qsort { //main函数，用于测试 public static void main(String[] args) { //手动创建数组，用于测试 int[] arr = new int[] {1,5,99,-29,698,-111,0,63,88,3,3,7,1,-8,7,256}; //若数组为空，长度<2等情况，无需排序 if(arr == null || arr.length < 2) { return; } //使用快速排序，传入数组头部和尾部下标 quickSort(0, arr.length-1, arr); for(int i = 0;i < arr.length;++i) { System.out.print(arr[i] + " "); } } //快速排序函数： public static void quickSort(int L, int R, int[] arr) { //下表不越界情况下：进行基准选取、划分、递归排序 if(L < R) { //使用random函数，随机选取一个元素作为基准，使得复杂度总是O(n log n) swap(R, L + (int)(Math.random() * (R - L + 1)), arr); //进行划分，获取到两个边界值：小于基准的边界less，大于基准的边界more //p[0] = less + 1 ，p[1] = more - 1 int[] p = partition(L, R, arr); //分别对划分后的子数组继续进行上述操作，是为递归排序 quickSort(L, p[0] - 1, arr); quickSort(p[1] + 1, R, arr); } } //划分函数： public static int[] partition(int L, int R, int[] arr) { //定义小于基准的边界less，大于基准的边界more int less = L - 1; int more = R; //从数组起始下标L开始遍历，直到超过大于基准的边界more，即下标越界 while(L < more) { //当前元素小于基准，与less边界外的元素交换，less边界扩展1位，下一元素作为当前元素 if(arr[L] < arr[R]) { swap(++less, L++, arr); //当前元素大于基准，与more边界外的元素交换，more边界扩展1位，交换后，当前元素未被比较，无需后移 }else if(arr[L] > arr[R]) { swap(--more, L, arr); //等于基准，无需交换，直接后移 }else { ++L; } } //划分完成后，将数组末尾的基准元素与more边界位置元素交换，真正的more边界变为more + 1 swap(more, R, arr); //将边界存入数组返回： return new int[] {less + 1, more}; } //交换函数： public static void swap(int a, int b, int[] arr) { int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } }
⚪复杂度
复杂度分析：
- 时间复杂度： 平均情况下为O(n log n)，最坏情况为O(n^2)。快速排序的性能高度依赖于选择的基准元素。
- 空间复杂度： O(log n) - 快速排序是一种原地排序算法，只需要常数级别的额外空间用于递归调用的栈。
🚀堆排序
⚪步骤
堆排序：
堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法，它利用堆的性质进行排序。堆是一个完全二叉树，可以分为最大堆和最小堆两种类型。在最大堆中，父节点的值大于或等于其子节点的值；而在最小堆中，父节点的值小于或等于其子节点的值。
以下是堆排序的详细步骤：
详细步骤：
- 建堆（Heapify）：
- 将待排序的数组构建成一个堆。建堆的过程是从最后一个非叶子节点开始，依次向上调整各个子树，使其满足堆的性质。
- 排序：
- 交换堆顶元素（最大或最小元素）和堆的最后一个元素，然后将堆的大小减 1。
- 再次调整堆，使其满足堆的性质。
- 重复上述步骤，直到堆的大小为 1，排序完成。
⚪实现
代码实现：
public class heapSortTest { //main函数、测试用 public static void main(String[] args) { int[] arr = new int[]{1,5,88,9,-88,-99,-685,78,4,3,3,7,1,-8,7,256}; heapSort(arr); for(int i = 0;i < arr.length;++i) { System.out.print(arr[i] + " "); } } // 堆排序，排序函数 public static void heapSort(int[] arr) { if(arr == null || arr.length < 2) return; for(int i = arr.length - 1; i >= 0; --i) { heapify(arr, i, arr.length - 1); } int heapSize = arr.length; swap(arr, 0, --heapSize); while(heapSize > 0) { heapify(arr, 0, heapSize); swap(arr, 0, --heapSize); } } //heapify，建堆函数 public static void heapify(int[] arr, int index, int heapSize) { //获取左孩子下标 int left = 2 * index + 1; //left < heapSize : 当前节点存在左孩子 while(left < heapSize) { // 获取左孩子、右孩子中最大值 int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left; // 较大孩子元素与父节点元素比较，更新较大值下标 largest = arr[index] < arr[largest] ? largest : index; // 父节点最大，无法下移，直接停止 if(index == largest) break; // 父节点小于较大孩子，下移 swap(arr, index, largest); // 维护父节点和左孩子 index = largest; left = 2 * index + 1; } } //交换函数 public static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
⚪复杂度
复杂度分析：
- 时间复杂度： 建堆操作的时间复杂度为O(n)，排序操作的时间复杂度为O(n log n)。因此，堆排序的总体时间复杂度为O(n log n)。
- 空间复杂度： 堆排序是一种原地排序算法，只需使用常数级别的额外空间，因此空间复杂度为O(1)。
🚀912. 排序数组
[⚪点击跳转【LeetCode 912. 排序数组】](912. 排序数组 - 力扣（LeetCode）)
题目：
给你一个整数数组
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]
提示：
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
解法一：归并排序：
//使用归并排序 class Solution { public int[] sortArray(int[] nums) { int length = nums.length; mergeSort(nums,0,nums.length - 1); return nums; } public void mergeSort(int[] arr,int l,int r){ //子数组长度为1，停止 if(l == r) return; //取中点 int mid = l + ((r - l) >> 1); //递归排序左子数组 mergeSort(arr,l,mid); //递归排序右子数组 mergeSort(arr,mid + 1,r); //合并两个排序好的数组 merge(arr,l,mid,r); } public void merge(int[] arr,int l,int mid,int r){ //help数组 int[] help = new int[r - l + 1]; //help数组下标 int i = 0; //左子数组头p1 int p1 = l; //右子数组头p2 int p2 = mid + 1; //合并两个有序数组，存入help数组 while(p1 <= mid && p2 <= r){ help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } while(p1 <= mid){ help[i++] = arr[p1++]; } while(p2 <= r){ help[i++] = arr[p2++]; } //将help数组的元素赋值回目标数组 for(int j = 0;j < help.length;++j){ arr[l + j] = help[j]; } } }
解法二：快速排序：
class Solution { //快排 public int[] sortArray(int[] nums) { if(nums == null || nums.length < 2) return nums; //空或长度1，无需排序 qSort(nums,0,nums.length - 1); //快排 return nums; } public static void qSort(int[] arr,int l,int r){ //数组头尾不冲突 if(l < r){ //利用random等概率随机获取基准 与尾部元素交换位置 swap(arr,r,l + (int)(Math.random() * (r - l + 1))); //得到长度二的数组，两个元素分别代表大于基准元素与小于基准元素的边界 int[] p = partition(arr,l,r); qSort(arr,l,p[0]); qSort(arr,p[1],r); } } //划分函数 public static int[] partition(int[] arr,int l,int r){ int less = l - 1; //小于基准的边界 int more = r; //大于基准的边界 while(l < more){ if(arr[l] < arr[r]){ swap(arr,++less,l++); }else if(arr[l] > arr[r]){ swap(arr,--more,l); }else{ ++l; } } swap(arr,more,r); return new int[]{less,more + 1}; } //交换 public static void swap(int[] arr,int a,int b){ int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } }
解法三：堆排序：
class Solution { public int[] sortArray(int[] nums) { heapSort(nums); return nums; } public static void heapSort(int[] arr){ if(arr == null || arr.length < 2) return; for(int i = arr.length - 1; i >= 0; --i){ heapify(arr, i, arr.length); } int heapSize = arr.length; swap(arr, 0, --heapSize); while(heapSize > 0){ heapify(arr, 0, heapSize); swap(arr, 0, --heapSize); } } public static void heapify(int[] arr, int index, int heapSize){ int left = 2 * index + 1; while(left < heapSize){ int largest = left + 1 < heapSize && arr[left] < arr[left+1] ? left + 1 : left; largest = arr[index] < arr[largest] ? largest : index; if(largest == index) break; swap(arr, index, largest); index = largest; left = 2 * index + 1; } } public static void swap(int[] arr, int a, int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
🚀315. 计算右侧小于当前元素的个数
给你一个整数数组
nums，按要求返回一个新数组counts。数组counts有该性质：counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。示例 1：
输入：nums = [5,2,6,1] 输出：[2,1,1,0] 解释： 5 的右侧有 2 个更小的元素 (2 和 1) 2 的右侧仅有 1 个更小的元素 (1) 6 的右侧有 1 个更小的元素 (1) 1 的右侧有 0 个更小的元素
示例 2：
输入：nums = [-1] 输出：[0]
示例 3：
输入：nums = [-1,-1] 输出：[0,0]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
利用归并排序性质，完成计数：
// 利用归并排序的特性， 计算 nums[i] 右侧小于 nums[i] 的元素的数量。 class Solution { static int[] counts; // 题目要求的counts数组 static int[] index; // 下标数组，记录nums元素的移动，即：元素移动，下标做同样操作。 public List<Integer> countSmaller(int[] nums) { List<Integer> list = new ArrayList<>(); //创建集合，因为:函数返回值为List<Integer> if(nums == null) return list; //数组为空，直接返回空集合 if(nums.length == 1){ //数组长度=1 list.add(0); //右侧没有小于nums[i]的元素，所以nums[i]=0，添加到集合中 return list; //直接返回 } //初始化counts和index int n = nums.length; this.counts = new int[n]; this.index = new int[n]; //为下标数组元素 附上 下标值 for(int i = 0;i < n; ++i){ index[i] = i; } //进行归并排序，在排序过程中完成计数 mergeSort(nums, 0, n - 1); //将得到的符合规则的counts数组元素赋值给集合再返回，因为:函数返回值为List<Integer> for(int count : counts) list.add(count); return list; } //归并排序： public static void mergeSort(int[] arr, int l, int r){ if(l == r) return; int mid = l + ((r - l) >> 1); mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } //合并有序子序列 public static void merge(int[] arr, int l, int mid, int r){ int[] help = new int[r - l + 1]; //元素的help数组，用于合并有序子序列 int[] helpI = new int[r - l + 1]; //下标的help数组，用于记录合并有序子序列时元素的移动 int i = 0; //下标 int p1 = l; //左子序列头元素下标 int p2 = mid + 1; //右子序列头元素下标 while(p1 <= mid && p2 <= r){ //按照逆序，进行归并排序的合并 if(arr[p1] > arr[p2]){ //因为逆序，所以p2到R范围内的元素是降序的，即： //当前情况下nums[i] 右侧小于 nums[i] 的元素的数量 = r - p2 + 1 //在排序过程中，累加所有情况下的r - p2 + 1，就能的到总数。 counts[index[p1]] += r - p2 + 1; help[i] = arr[p1]; helpI[i++] = index[p1++]; }else{ help[i] = arr[p2]; helpI[i++] = index[p2++]; } } while(p1 <= mid){ help[i] = arr[p1]; helpI[i++] = index[p1++]; } while(p2 <= r){ help[i] = arr[p2]; helpI[i++] = index[p2++]; } //将help数组中的元素 赋值回原数组中，完成合并。 for(i = 0;i < help.length; ++i){ arr[i + l] = help[i]; index[i + l] = helpI[i]; } } }
🚀561. 数组拆分
给定长度为
2n的整数数组nums，你的任务是将这些数分成n对, 例如(a1, b1), (a2, b2), ..., (an, bn)，使得从1到n的min(ai, bi)总和最大。返回该 最大总和 。
示例 1：
输入：nums = [1,4,3,2] 输出：4 解释：所有可能的分法（忽略元素顺序）为： 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 所以最大总和为 4
示例 2：
输入：nums = [6,2,6,5,1,2] 输出：9 解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9
提示：
1 <= n <= 104nums.length == 2 * n-104 <= nums[i] <= 104
题解（归并排序）：
//归并排序 class Solution { public int arrayPairSum(int[] nums) { //排序数组（这里使用归并排序，还推荐使用堆排序、快速排序） mergeSort(nums, 0, nums.length - 1); //根据分析，有序的数组分成n对，就能满足题意 int ans = 0; for(int i = 0;i < nums.length; i += 2){ //将每队的min(ai, bi)累加起来，得到总和 ans += nums[i]; } //返回结果 return ans; } public static void mergeSort(int[] arr, int l, int r){ if(l == r) return; int mid = l + ((r - l) >> 1); mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } public static void merge(int[] arr, int l,int mid, int r){ int[] help = new int[r - l + 1]; int p1 = l; int p2 = mid + 1; int i = 0; while(p1 <= mid && p2 <= r){ help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } while(p1 <= mid){ help[i++] = arr[p1++]; } while(p2 <= r){ help[i++] = arr[p2++]; } for(i = 0;i < help.length; ++i){ arr[i + l] = help[i]; } } }
题解（堆排序）：
class Solution { public int arrayPairSum(int[] nums) { int n = nums.length; heapSort(nums, n); //堆排序 int ans = 0; for(int i = 0;i < n; i += 2){ ans += nums[i]; } return ans; } public static void heapSort(int[] arr, int n){ if(arr == null || n < 2) return; for(int i = n - 1; i >= 0; --i){ heapify(arr, i, n); } int heapSize = n; swap(arr, 0, --heapSize); while(heapSize > 0){ heapify(arr, 0, heapSize); swap(arr, 0, --heapSize); } } public static void heapify(int[] arr, int index, int heapSize){ int left = 2 * index + 1; while(left < heapSize){ int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; largest = arr[index] > arr[largest] ? index : largest; if(index == largest) break; //无法下移，停止 swap(arr, index, largest); //可以下移，交换 index = largest; //交换完后完成下移 left = 2 * index + 1; //维护左孩子 } } public static void swap(int[] arr, int a, int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
题解（快速排序）【速度最快】：
class Solution { public int arrayPairSum(int[] nums) { int n = nums.length; quickSort(nums, 0, n - 1); int ans = 0; for(int i = 0;i < n; i += 2){ ans += nums[i]; } return ans; } public static void quickSort(int[] arr, int l, int r){ if(l < r){ swap(arr, r, l + (int)(Math.random() * (r - l + 1))); int[] p = partition(arr, l, r); quickSort(arr, l, p[0]); quickSort(arr,p[1], r); } } public static int[] partition(int[] arr, int l, int r){ int less = l - 1; int more = r; while(l < more){ if(arr[l] < arr[r]){ swap(arr, ++less, l++); }else if(arr[l] > arr[r]){ swap(arr, --more, l); }else{ ++l; } } swap(arr, more, r); return new int[]{less, more + 1}; } public static void swap(int[] arr, int a, int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
🚀1122. 数组的相对排序（计数排序）
给你两个数组，
arr1和arr2，arr2中的元素各不相同，arr2中的每个元素都出现在arr1中。对
arr1中的元素进行排序，使arr1中项的相对顺序和arr2中的相对顺序相同。未在arr2中出现过的元素需要按照升序放在arr1的末尾。示例 1：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 输出：[2,2,2,1,4,3,3,9,6,7,19]
示例 2:
输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6] 输出：[22,28,8,6,17,44]
提示：
1 <= arr1.length, arr2.length <= 10000 <= arr1[i], arr2[i] <= 1000arr2中的元素arr2[i]各不相同arr2中的每个元素arr2[i]都出现在arr1中
题解（计数排序）：
计数排序是一种非比较性的整数排序算法，适用于待排序元素的范围较小的情况。该算法的基本思想是统计每个元素的出现次数，然后根据这些统计信息将元素放回正确的位置。
class Solution { //计数排序 public int[] relativeSortArray(int[] arr1, int[] arr2) { //题目给定元素大小不超过1000，就可以设置一个1001长度的数组来进行计数排序 int[] arr = new int[1001]; //计数数组 int[] ans = new int[arr1.length]; //排序数组 int index = 0; //排序数组的下标 //遍历arr1，遍历到元素，就使arr数组对应下标的值+1 for(int num : arr1){ arr[num] += 1; } //遍历arr2数组，先将与arr2相对顺序元素放入排序数组 for(int num : arr2){ for(int i = 0;i < arr[num]; ++i){ ans[index++] = num; } arr[num] = 0; //维护计数数组 } //遍历计数数组，将剩下的元素排序好并放入排序数组 for(int k = 0;k < 1001; ++k){ for(int i = 0;i < arr[k]; ++i){ ans[index++] = k; } } return ans; } }
🚀268. 丢失的数字（计数排序）
给定一个包含
[0, n]中n个数的数组nums，找出[0, n]这个范围内没有出现在数组中的那个数。示例 1：
输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1] 输出：2 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1] 输出：8 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
提示：
n == nums.length1 <= n <= 1040 <= nums[i] <= nnums中的所有数字都 独一无二
题解（计数排序）
class Solution { public int missingNumber(int[] nums) { int ans = -1; //没有出现在数组中的那个数。 int n = nums.length; //题目提到的n int[] arr = new int[n + 1]; //计数数组，用于记录元素出现的次数 for(int num : nums){ //使用计数数组，记录并排序nums数组元素 arr[num] += 1; } for(int i = 0;i <= n; ++i){ //遍历计数数组，值为0表示未出现 if(arr[i] == 0){ ans = i; break; } } return ans; } }
🚀215. 数组中的第K个最大元素
给定整数数组
nums和整数k，请返回数组中第**k**个最大的元素。请注意，你需要找的是数组排序后的第
k个最大的元素，而不是第k个不同的元素。你必须设计并实现时间复杂度为
O(n)的算法解决此问题。示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
题解（快速排序）：
class Solution { public int findKthLargest(int[] nums, int k) { quickSort(nums, 0, nums.length - 1); int ans = Integer.MIN_VALUE; for(int i = 0;i <= nums.length - k; ++i){ ans = nums[i]; } return ans; } public static void quickSort(int[] arr, int l, int r){ if(l < r){ swap(arr, r, l + (int)(Math.random() * (r - l))); int[] p = partition(arr, l, r); quickSort(arr, l, p[0]); quickSort(arr, p[1], r); } } public static int[] partition(int[] arr, int l, int r){ int less = l - 1; int more = r; while(l < more){ if(arr[l] < arr[r]){ swap(arr, ++less, l++); }else if(arr[l] > arr[r]){ swap(arr, --more, l); }else{ ++l; } } swap(arr, more, r); return new int[]{less, more + 1}; } public static void swap(int[] arr, int a, int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
🚀347. 前 K 个高频元素
给你一个整数数组
nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按 任意顺序 返回答案。示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
题解（优先队列[堆排序] + hash表）：
class Solution { public int[] topKFrequent(int[] nums, int k) { PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (b[1] - a[1])); Map<Integer, Integer> map = new HashMap<>(); int[] ans = new int[k]; for(int num : nums){ if(!map.containsKey(num)){ map.put(num,1); }else{ map.put(num,map.get(num).intValue() + 1); } } for(Map.Entry<Integer, Integer> entry : map.entrySet()){ pq.offer(new int[]{entry.getKey(), entry.getValue()}); } for(int i = 0;i < k; ++i){ ans[i] = pq.poll()[0]; } return ans; } }
🚀LCR 159. 库存管理 III(计数排序)
仓库管理员以数组
stock形式记录商品库存表，其中stock[i]表示对应商品库存余量。请返回库存余量最少的cnt个商品余量，返回 顺序不限。示例 1：
输入：stock = [2,5,7,4], cnt = 1 输出：[2]
示例 2：
输入：stock = [0,2,3,6], cnt = 2 输出：[0,2] 或 [2,0]
提示：
0 <= cnt <= stock.length <= 10000 0 <= stock[i] <= 10000
题解（计数排序）：
class Solution { public int[] inventoryManagement(int[] stock, int cnt) { int[] help = new int[10001]; for(int num : stock){ help[num] += 1; } int[] ans = new int[cnt]; int index = 0; a:for(int i = 0;i < 10001; ++i){ for(int j = 0;j < help[i]; ++j){ if(index < cnt){ ans[index++] = i; }else{ break a; } } } return ans; } }
题解（快速排序）：
class Solution { public int[] getLeastNumbers(int[] arr, int k) { int[] ans = new int[k]; qSort(arr,0,arr.length - 1); for(int i = 0;i < k;++i){ ans[i] = arr[i]; } return ans; } public static void qSort(int[] arr,int l,int r){ if(l < r){ swap(arr,r,l + (int)(Math.random() * (r - l + 1))); int[] p = partition(arr,l,r); qSort(arr,l,p[0]-1); qSort(arr,p[1]+1,r); } } public static int[] partition(int[] arr,int l,int r){ int less = l - 1; int more = r; while(l < more){ if(arr[l] < arr[r]){ swap(arr,++less,l++); }else if(arr[l] > arr[r]){ swap(arr,l,--more); }else{ ++l; } } swap(arr,r,more); return new int[]{less+1,more}; } public static void swap(int[] arr,int a,int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
🚀LCR 170. 交易逆序对的总数
在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录
record，返回其中存在的「交易逆序对」总数。示例 1:
输入：record = [9, 7, 5, 4, 6] 输出：8 解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
限制：
0 <= record.length <= 50000
归并排序 题解：
class Solution { int ans = 0; public int reversePairs(int[] record) { if(record == null || record.length < 2) return ans; mergeSort(record, 0, record.length - 1); return ans; } public void mergeSort(int[] arr, int l, int r){ if(l == r) return; int mid = l + ((r - l) >> 1); mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } public void merge(int[] arr, int l, int mid, int r){ int[] help = new int[r - l + 1]; int p1 = l; int p2 = mid + 1; int i = 0; while(p1 <= mid && p2 <= r){ if(arr[p1] > arr[p2]){ ans += r - p2 + 1; help[i++] = arr[p1++]; }else{ help[i++] = arr[p2++]; } } while(p1 <= mid){ help[i++] = arr[p1++]; } while(p2 <= r){ help[i++] = arr[p2++]; } for(i = 0;i < help.length; ++i){ arr[i + l] = help[i]; } } }
