Java Study!! - 差分
type: channel
link: https://www.kaijavademo.top/tag/%E5%B7%AE%E5%88%86/
items: 算法题：基础算法篇

算法题：基础算法篇
type: item
date: 2023-08-23T13:12:00+00:00
description: 这里是我刷算法题的笔记，来自于acwing，我会将我做算法题的心得和改进写在笔记中用于分享和交流，你也可以和我一起刷一起交流。AcWing 786. 第k个数题目一开始我想到的是，用快排，然后遍历做一个判断(看起来笨笨的，新手只能想到这个QAQ)import java.util.Scanner; import java.util.stream.IntStream; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] arr = IntStream.range(0,n).map(i -> sc.nextInt()).toArray(); int[] sortedArr = quickSort(arr,0,n-1); for(int i = 0; i < sortedArr.length; i++){ if(i == (k-1)){ System.out.println(sortedArr[i]); } } } private static int[] quickSort(int[] q,int l,int r){ if(l >= r) return q; int p = q[l+ r >>1],i = l-1,j = r+1; while(i<j){ while(q[++i] < p); while(q[--j] > p); if(i<j){ int t = q[i]; q[i] = q[j]; q[j] = t; } } quickSort(q,l,j); quickSort(q,j+1,r); return q; } }这样写勉勉强强过了，但是这样处理笨笨的，我在看了y总的题解之后知道这道题有一种更好的办法。实际上我们先回顾快排的步骤确定分解点（一共有四种，听说现在使用中点和随机不会超时）处理分界点左边和右边的数，保证左边的最大值小于右边的最小值，当然分界点的元素相同的话分布在左右两边递归处理左边和右边的数快排的时间复杂度平均是 [label color="blue"]O(nlogn)[/label] ,这道题其实上使用的是快速选择排序。我们可以这样考虑，找第k个数，无非是在处理完分解点之后，将一组数分成两部分，我们可以比较第k个数的位置，那么此会产生两种情况当左区间的个数sl大于k，说明k在左边当左区间的个数sl小于k，说明k在右边。此时k在右边的位置应该是k-sl。通过这两种思路我们只需要把k作为形参放在快排方法中，方法的第三步我们稍作调整，递归中加入k，根据不同的情况返回不同的递归值。如果遍历有右区间，那么应该寻找的是第k - sl个数。 [label color="red"]会保证第k小的数一直在递归的区间中，那么当区间里只有一个数的时候，就一定是要找的数了。[/label] 那么我们需要调整返回值，和一开始的出口返回数组的左边界（q[l]）即可。import java.util.Scanner; import java.util.stream.IntStream; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] arr = IntStream.range(0,n).map(i -> sc.nextInt()).toArray(); System.out.println(quickSort(arr,0,n-1,k)); } private static int quickSort(int[] q,int l,int r, int k){ if(l >= r) return q[l]; int p = q[l+ r >>1],i = l-1,j = r+1; while(i<j){ while(q[++i] < p); while(q[--j] > p); if(i<j){ int t = q[i]; q[i] = q[j]; q[j] = t; } } //计算左区间的长度 int sl = j - l + 1; //始终保持k在递归区间，当区间只有一个数的时候,那么就是我们要找的数 if(sl >= k){ return quickSort(q,l,j,k); }else{ return quickSort(q,j+1,r,k-sl); }…