①归并排序、快速排序 、堆排序、计数排序[算法、代码模板、面试题]

在这里插入图片描述

个人简介：Java领域新星创作者；阿里云技术博主、星级博主、专家博主；正在Java学习的路上摸爬滚打，记录学习的过程~
个人主页：.29.的博客
学习社区：进去逛一逛~

在这里插入图片描述

排序[算法、代码模板、面试题]

  • ①归并排序、快速排序 、堆排序、计数排序
    • 🚀归并排序
      • ⚪步骤
      • ⚪实现
      • ⚪复杂度
    • 🚀快速排序
      • ⚪步骤
      • ⚪实现
      • ⚪复杂度
    • 🚀堆排序
      • ⚪步骤
      • ⚪实现
      • ⚪复杂度
    • 🚀912. 排序数组
    • 🚀315. 计算右侧小于当前元素的个数
    • 🚀561. 数组拆分
    • 🚀1122. 数组的相对排序（计数排序）
    • 🚀268. 丢失的数字（计数排序）
    • 🚀215. 数组中的第K个最大元素
    • 🚀347. 前 K 个高频元素
    • 🚀LCR 159. 库存管理 III(计数排序)
    • 🚀LCR 170. 交易逆序对的总数

①归并排序、快速排序 、堆排序、计数排序

🚀归并排序

⚪步骤

归并排序：

归并排序是一种分治法（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) / 2process(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）是一种常用的基于分治思想的排序算法。它的基本思想是通过一趟排序将待排序的记录分割成独立的两部分，其中一部分的所有记录均比另一部分的记录小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。快速排序的核心是选择一个基准元素，将小于等于基准的元素放在左边，大于基准的元素放在右边，然后对左右两个子序列分别递归地应用相同的方法。


详细步骤：

  1. 选择基准元素：
    • 从待排序数组中选择一个元素作为基准元素。通常选择第一个元素、最后一个元素或者中间元素。（本文等概率随机选取一个元素作为基准，避免最坏复杂度的发生）
  2. 分区（Partition）：
    • 将数组中小于等于基准的元素放在基准的左边，大于基准的元素放在右边。这一步通常称为分区操作。
    • 使用两个指针，一个在数组的起始位置，一个在数组的结束位置，分别向中间移动，交换不符合条件的元素，直到两个指针相遇。
  3. 递归排序：
    • 对基准左右两侧的子数组进行递归排序。重复以上步骤，直到每个子数组的大小为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 - 1int[] 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，大于基准的边界moreint 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 + 1swap(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）是一种基于二叉堆数据结构的排序算法，它利用堆的性质进行排序。堆是一个完全二叉树，可以分为最大堆和最小堆两种类型。在最大堆中，父节点的值大于或等于其子节点的值；而在最小堆中，父节点的值小于或等于其子节点的值。

以下是堆排序的详细步骤：


详细步骤：

  1. 建堆（Heapify）：
    • 将待排序的数组构建成一个堆。建堆的过程是从最后一个非叶子节点开始，依次向上调整各个子树，使其满足堆的性质。
  2. 排序：
    • 交换堆顶元素（最大或最小元素）和堆的最后一个元素，然后将堆的大小减 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;//左子数组头p1int p1 = l;//右子数组头p2int 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. 计算右侧小于当前元素的个数

⚪点击跳转：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){                   //数组长度=1list.add(0);      //右侧没有小于nums[i]的元素，所以nums[i]=0，添加到集合中return list;      //直接返回}//初始化counts和indexint 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. 数组拆分

⚪点击跳转：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 <= 104
  • nums.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. 数组的相对排序（计数排序）

⚪点击跳转：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 <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2 中的元素 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数组对应下标的值+1for(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. 丢失的数字（计数排序）

⚪点击跳转：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.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二



题解（计数排序）

class Solution {public int missingNumber(int[] nums) {int ans = -1;               //没有出现在数组中的那个数。int n = nums.length;        //题目提到的nint[] 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个最大元素

⚪点击跳转：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 个高频元素

⚪点击跳转：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 <= 105
  • k 的取值范围是 [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(计数排序)

⚪点击跳转：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. 交易逆序对的总数

⚪点击跳转：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];}}
}



在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/210637.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

波奇学C++：类型转换和IO流

波奇学C++：类型转换和IO流

隐式类型转换 int i0; double pi; 强制类型转换 int* pnullptr; int a(int)p; 单参数构造函数支持隐式类型转换 class A { public:A(string a):_a(a){} private:string _a; }; A a("xxxx"); //"xxx" const char* 隐式转换为string 多参数也可以通过{…
阅读更多...
【6】PyQt信号和槽

【6】PyQt信号和槽

1. 信号和槽简介 信号和槽机制是 QT 的核心机制&#xff0c;应用于对象之间的通信 信号和槽是用来在对象间传递数据的方法当一个特定事件发生的时候&#xff0c;signal会被emit出来&#xff0c;slot调用是用来响应相应的signal的Qt中对象已经包含了许多预定义的 signal&#…
阅读更多...
Android进阶之路 - TextView文本渐变

Android进阶之路 - TextView文本渐变

那天做需求的时候&#xff0c;遇到一个小功能&#xff0c;建立在前人栽树&#xff0c;后人乘凉的情况下&#xff0c;仅用片刻就写完了&#xff1b;说来惭愧&#xff0c;我以前并未写过文本渐变的需求&#xff0c;脑中也仅有一个shape渐变带来的大概思路&#xff0c;回头来看想着…
阅读更多...
Web网页安全策略的研究及其实现方案

Web网页安全策略的研究及其实现方案

摘 要 越来越多的人使用电脑来接触互联网&#xff0c;事实上&#xff0c;使用Web技术的实现基于网络的不断完善和发展的交流网站&#xff0c;人们可以利用计算机网络技术&#xff0c;方便得到想要的任何信息。计算机网络的发展&#xff0c;也促进了相关产业的发展&#xff0c;…
阅读更多...
【vue-router】useRoute 和 useRouter 的区别

【vue-router】useRoute 和 useRouter 的区别

&#x1f680; 作者主页&#xff1a; 有来技术 &#x1f525; 开源项目&#xff1a; youlai-mall &#x1f343; vue3-element-admin &#x1f343; youlai-boot &#x1f33a; 仓库主页&#xff1a; Gitee &#x1f4ab; Github &#x1f4ab; GitCode &#x1f496; 欢迎点赞…
阅读更多...
5个超实用GPT技巧，包括绩效总结、头脑风暴、营销策略等（内附提示词）

5个超实用GPT技巧，包括绩效总结、头脑风暴、营销策略等（内附提示词）

今天和大家分享5个用于工作上的GPT技巧&#xff0c;例如进行绩效总结、自我评估、头脑风暴&#xff0c;还是制作PPT方案等等&#xff0c;最大化提升你工作效率&#xff0c;本期内容对于大家来说都非常受用&#xff0c;记得收藏起来哦&#xff01; 那么接下来就直接进入正题吧&a…
阅读更多...
postgresql pg_hba.conf 配置详解

postgresql pg_hba.conf 配置详解

配置文件之pg_hba.conf介绍 该文件用于控制访问安全性&#xff0c;管理客户端对于PostgreSQL服务器的访问权限&#xff0c;内容包括&#xff1a;允许哪些用户连接到哪个数据库&#xff0c;允许哪些IP或者哪个网段的IP连接到本服务器&#xff0c;以及指定连接时使用的身份验证模…
阅读更多...
Leetcode—205.同构字符串【简单】

Leetcode—205.同构字符串【简单】

2023每日刷题&#xff08;五十&#xff09; Leetcode—205.同构字符串 算法思想 参考自k神思路 实现代码 class Solution { public:unordered_map<char, char> s2t, t2s;bool isIsomorphic(string s, string t) {int n s.size();for(int i 0; i < n; i) {char …
阅读更多...
梦回吹角连营(2)(快速幂快乘)

梦回吹角连营(2)(快速幂快乘)

Description 给定f(n)(a1)*n^a(a2)*n^(a1)...b*n^(b-1) 求f(n)%10000000033 Input 输入一个正整数T(T<10),表示有T组数据&#xff0c;每组数据包括三个整数a,b,n (0<n<10^9,1<a < b-1<10^20) Output 输出 f(n)%10000000033 的结果 Sample Input 1 1 2…
阅读更多...
抽奖.html(网上收集8)

抽奖.html(网上收集8)

<!doctype html> <html> <head><meta charset"utf-8"><title>在线抽奖 随机选取 自动挑选</title><script src"https://libs.baidu.com/jquery/1.10.2/jquery.min.js"></script><style>body {backg…
阅读更多...
基于Springboot的秒杀系统（有报告）。Javaee项目，springboot项目。

基于Springboot的秒杀系统（有报告）。Javaee项目，springboot项目。

演示视频&#xff1a; 基于Springboot的秒杀系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xf…
阅读更多...
【Linux】ln命令使用

【Linux】ln命令使用

ln命令 ln是linux中又一个非常重要命令&#xff0c;请大家一定要熟悉。它的功能是为某一个文件在另外一个位置建立一个同步的链接&#xff0c;这个命令最常用的参数是-s&#xff0c;具体用法是&#xff1a;ln –s 源文件 目标文件。 当我们需要在不同的目录&#xff0c;用到相…
阅读更多...
【4】PyQt输入框

【4】PyQt输入框

1. 单行文本输入框 QLineEdit控件可以输入单行文本 from PyQt5.QtWidgets import QApplication, QWidget, QLineEdit, QVBoxLayout from PyQt5.QtCore import * from PyQt5.QtGui import QIcon import sysdef init_widget(w: QWidget):# 修改窗口标题w.setWindowTitle(单行输…
阅读更多...
【Spark入门】基础入门

【Spark入门】基础入门

【大家好&#xff0c;我是爱干饭的猿&#xff0c;本文重点介绍Spark的定义、发展、扩展阅读&#xff1a;Spark VS Hadoop、四大特点、框架模块、运行模式、架构角色。 后续会继续分享其他重要知识点总结&#xff0c;如果喜欢这篇文章&#xff0c;点个赞&#x1f44d;&#xff…
阅读更多...
【Openstack Train安装】五、Memcached/Etcd安装

【Openstack Train安装】五、Memcached/Etcd安装

本文介绍Memcached/Etcd安装步骤&#xff0c;Memcached/Etcd仅需在控制节点安装。 在按照本教程安装之前&#xff0c;请确保完成以下配置&#xff1a; 【Openstack Train安装】一、虚拟机创建 【Openstack Train安装】二、NTP安装 【Openstack Train安装】三、openstack安装…
阅读更多...
持续集成交付CICD：CentOS 7 安装 Sonarqube9.6

持续集成交付CICD：CentOS 7 安装 Sonarqube9.6

目录 一、实验 1.CentOS 7 安装 Sonarqube9.6 二、问题 1.安装postgresql13服务端报错 2.postgresql13创建用户报错 3.bash: sonar-scanner: 未找到命令 一、实验 1.CentOS 7 安装 Sonarqube9.6 &#xff08;1&#xff09;下载软件及依赖包 ①Sonarqube9.6下载地址 h…
阅读更多...
C/C++，图算法——求强联通的Tarjan算法之源程序

C/C++，图算法——求强联通的Tarjan算法之源程序

1 文本格式 #include <bits/stdc.h> using namespace std; const int maxn 1e4 5; const int maxk 5005; int n, k; int id[maxn][5]; char s[maxn][5][5], ans[maxk]; bool vis[maxn]; struct Edge { int v, nxt; } e[maxn * 100]; int head[maxn], tot 1; vo…
阅读更多...
Vellum —— 相关特点

Vellum —— 相关特点

目录 Cloth Breaking and tearing Paneling and draping Cloth simulation Calculating mass and thickness Working with low res and high res cloth Quick moving cloth Softbody Vellum softbodies Plasticity with softbodies Constraints Stitch and slid…
阅读更多...
Centos7 制作Openssh9.5 RPM包

Centos7 制作Openssh9.5 RPM包

Centos7 制作Openssh9.5 RPM包 最近都在升级Openssh版本到9.3.在博客里也放了openssh 9.5的rpm包. 详见:https://blog.csdn.net/qq_29974229/article/details/133878576 但还是有小伙伴不停追问这个rpm包是怎么做的,怕下载别人的rpm包里被加了盐. 于是做了个关于怎么用官方的o…
阅读更多...
yolov8添加ca注意力机制

yolov8添加ca注意力机制

创建文件 coordAtt.py 位置&#xff1a;ultralytics/nn/modules/coordAtt.py ###################### CoordAtt #### start by AI&CV ############################### # https://zhuanlan.zhihu.com/p/655475515 import torch import torch.nn as nn import t…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023