题目描述 现有一个包含n个整数（1<=n<=900000）的无序序列(保证序列内元素各不相同)， 输入一个整数k（1<=k<=n）,请用较快的方式找出该序列的第k小数并输出。
Input 多组输入。 首先输入一个数据组数T（1<=T<=100） 接下来是T组数据。 每组数据有两行。 第一行先输入两个整数，n和k。 接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000000)。
Output 对于每组数据，输出该组数据中第k小的数num。
Sample Input
2 6 4 3 2 5 1 4 6 10 4 3 2 10 11 2 33 5 1 4 6
Sample Output
4
/* */ package 快排及其应用; import java.util.Arrays; import java.util.Scanner; /** * @author JohnnyLin * @version Creation Time：2020年9月30日 下午7:03:03 */ public class 第k小数字_快排思想 { public static void main(String[] args) { Scanner reader=new Scanner(System.in); int T=reader.nextInt(); int a[]; while(T>0) { int n=reader.nextInt(); int k=reader.nextInt(); a=new int[n]; for(int i=0;i<n;i++) { a[i]=reader.nextInt(); } System.out.println(selectK(a,0,a.length-1,k)); T--; } } /** * @param a * @param l * @param r * @return 返回a[l]元素在原序列的下标位置 */ public static int partion(int []a,int l,int r) { int target=a[l]; int i=l; while(l<r) { while(l<r&&a[r]>=target) { r--; } while(l<r&&a[l]<=target) { l++; } if(l<r) {//左右指针均停下来 int tmp=a[l]; a[l]=a[r]; a[r]=tmp; } } int tmp=a[l]; a[l]=target; a[i]=tmp; return l; } public static int selectK(int []a,int l,int r,int k) { //System.out.println(l+"\t"+"\t"+r+"\t"); int position=partion(a, l, r); //System.out.println(position); //System.out.println(Arrays.toString(a)); if(position+1>k) {//目标在左侧 return selectK(a, l, position-1,k); }else if(position+1<k) {//目标在右侧 return selectK(a, position+1, r,k); }else { return a[position];// 将结果传给调用层 调用层逐层递传 } } }主定理最早出现在《算法导论》中，提供了分治方法带来的递归表达式的渐近复杂度分析。 规模为n的问题通过分治，得到a个规模为n/b的问题，然后每次递归带来在O(n^d)时间内将问题的解合并起来。 算法时间复杂度为：T(n)=a*T(n/b)+O(n^d)(其中a>0,b>1,d>=0) 那么就可以得到问题的复杂度为：
主定理b^d>a 时间复杂度为O(n^d)b^d==a 时间复杂度为O(n^d*logn)b^d<a 时间复杂度为O(n^(logb(a)))寻找第K小数字算法中使用了快速排序的partion函数快速找到中位数，理想状态下每次丢弃一半数据查找。不需要合并时间。 时间复杂度为：T(N)=T(N/2)+T(N/4)+T(N/8)+……+T(N/2^k) 则根据主定理公式，a=1,b=2,d=1 a<b^d 时间复杂度为O(n)
题目描述： 数组中一个数字出现的次数超过数组长度的一半，请找出这个数字。 例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。 由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2.
分析： 假设数组长度为N 1、O(log(N)*N)做法： 先排序后输出a[N/2]元素 2、两两不同元素消除：O(N)复杂度 3、顺序选择：超过一半的数字必是第N/2个小的数字，这种做法成立的条件是默认必有超过一半的数字存在 否则像1,2,3,4,5这样不存在超过一半的数字，会得出错误的解3。 4、计数排序：统计次数超过N/2的数字 O(N)复杂度，计数排序的缺点是不适合数据范围过大的，加入最大数为1亿，则要开辟[0,1 0000 0000]的数组空间，代价太大。
package 快排及其应用; /** * @author JohnnyLin * @version Creation Time：2020年9月30日 下午11:16:19 */ public class 超过一半的数 { //两两消除法 public static void morethanhalf_两两消除(int a[]) { int sameCnt=1; int before=a[0]; for(int i=1;i<a.length;i++) { //此时开始新的一轮两两比较 sameCnt记为1 if(sameCnt==0) { before=a[i]; sameCnt=1; continue; } if(before==a[i]) { sameCnt++; }else { sameCnt--; } } System.out.println(before); } public static void morethanhalf_计数排序(int a[]) { int max=a[0]; for (int i = 1; i < a.length; i++) { max=(a[i]>max)?a[i]:max; } //数组值范围：[0,max+1] int b[]=new int[max+1]; //遍历原序列 在b数组统计相应值出现的次数 for(int i=0;i<a.length;i++) { b[a[i]]++; } int k=a.length>>1; for (int i=0;i<b.length;i++) { if(b[i]>k) { System.out.println(i); } } } public static void main(String args[]) { int a[]= {1,2,4,4,4,4,4,3,2,2,4,4,4,2,5,4,4,4,4,2}; morethanhalf_两两消除(a); //超过一半的数字必是第a.length/2小 int k=第k小数字_快排思想.selectK(a,0,a.length-1,a.length/2); System.out.println(k); //计数排序 morethanhalf_计数排序(a); } }题目描述： Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说，Tango有一大“水王”，他不但喜欢发贴，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？
两两消除思想： 根据题目描述，一定存在水王，而水王的发帖数目一定超过一半。 那么可以使用消除法：可以认为水王面临着这样的挑战：假设第一 个是水王ID 其他ID都想与水王PK，水王遇到其他ID的贴子，贴子数就会减1 遇到自己的ID帖子数就加1，那么最后只有是水王的帖子数会大于0， 因为它的数目超过一半。
package 快排及其应用; /** * @author JohnnyLin * @version Creation Time：2020年10月4日 下午4:02:45 */ public class 寻找发帖水王 { public static void morethanhalf(int a[]) { int ntimes=1; int candidate=a[0]; for(int i=1;i<a.length;i++) { if(ntimes==0) {//重新更新水王的ID和发帖次数 candidate=a[i]; ntimes=1; continue; } //a[i]与水王ID不同 if(a[i]!=candidate) { ntimes--; }else { ntimes++; } } if(ntimes>0) System.out.println("水王ID："+candidate); } public static void main(String[] args) { //下面的测试数据是不通过的，原因是上述算法是默认水王是存在的， //是以存在一个ID它的发帖数超过一半为条件的 //int a[]= {1,2,3,4,5,6,7,8,9}; int a[]= {1,2,3,2,2,2,5}; morethanhalf(a); } }题目描述： 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求空间复杂度为O(1)
思路： 在快数排序的partion()函数中，利用双指针将原序列划分为以pivot为基准的两个区间 。左部分小于pivot ，右部分大于pivot。 同样的，这里也可以利用双指针将原序列 划分为前面为奇数后面为偶数 注意使用双指针交换 改变了原数组的相对顺序
package 快排及其应用; import java.util.Arrays; /** * @author JohnnyLin * @version Creation Time：2020年10月4日 下午5:21:47 */ public class 调整数组顺序_奇数位于偶数前 { public static void oddBeforeEven(int a[],int l,int r) { while(l<r) { //双指针没有交汇且a[r]是偶数 while(l<r&&isEven(a[r])) r--; while(l<r&&!isEven(a[l])) l++; if(l<r) {//两指针停下来且没有交汇 说明是l遇到了偶数 r遇到了奇数 int tmp=a[l]; a[l]=a[r]; a[r]=tmp; } } System.out.println(Arrays.toString(a)); } private static boolean isEven(int v) { return (v&1)==0; } public static void main(String[] args) { int a[]= {1,2,3,4,5,6,7,8,9,10}; oddBeforeEven(a, 0, a.length-1); } }题目描述： 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
做法1： 利用双指针l和r l将奇数从左到右存放到辅助数组helper r则将偶数从右到左存放到辅助数组helper 最后秩序调整右半段的顺序即可
package 分治思想及快排双指针分区的应用; import java.util.Arrays; /** * @author JohnnyLin * @version Creation Time：2020年10月4日 下午5:40:24 */ public class 调整数组顺序_要求不改变相对顺序 { public static void reOrderArray(int [] a) { if(a==null||a.length==0) return; int n=a.length; int helper[]=new int[n]; int i=0,j=n-1; for (int k = 0; k < n; k++) { if((a[k]&1)==0) {//偶数 helper[j--]=a[k]; }else {//奇数 helper[i++]=a[k]; } } j=n-1; while(i<j) { int tmp=helper[i]; helper[i]=helper[j]; helper[j]=tmp; i++; j--; } a=Arrays.copyOf(helper, helper.length); System.out.println(Arrays.toString(a)); } public static void main(String[] args) { int a[]= {1,2,3,4,5,6,7}; /* 1 2 3 4 5 6 7 * 1 3 2 4 5 6 7 * 1 3 2 5 4 6 7 * 1 3 5 2 4 6 7 * 1 3 5 2 4 7 6 * 1 3 5 7 2 4 6 */ //reOrderArray(a); reOrderArray2(a); } }做法2： 与冒泡排序类似 只要出现前偶后奇的情况我就交换.
public static void reOrderArray2(int [] a) { if(a==null||a.length==0) return; int n=a.length; /* 1 2 3 4 5 6 7 * 1 3 2 4 5 6 7 * 1 3 2 5 4 6 7 * 1 3 5 2 4 6 7 * 1 3 5 2 4 7 6 * 1 3 5 7 2 4 6 */ for(int i=0;i<n;i++) { for(int j=n-1;j>0;j--) { //前偶后奇则交换 if(isEven(a[j-1])&&!isEven(a[j])) { int tmp=a[j-1]; a[j-1]=a[j]; a[j]=tmp; } } } System.out.println(Arrays.toString(a)); } private static boolean isEven(int v) { return (v&1)==0; }给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
来源：力扣（LeetCode） 链接：合并两个有序数组
package 分治思想及快排双指针分区的应用; import java.util.Arrays; /** * @author JohnnyLin * @version Creation Time：2020年10月5日 下午9:44:19 */ public class 合并两个有序数组_辅助空间 { public static void merge(int[] nums1, int m, int[] nums2, int n) { if(nums2==null) { System.out.println(Arrays.toString(nums1)); return; } //备份nums1数组 int helper[]=new int[m]; helper=Arrays.copyOf(nums1, m); int i=0,j=0, k=0; //往nums1填充数据 for(;i<m&&j<n;) { if(helper[i]<=nums2[j]) { nums1[k++]=helper[i++]; }else { nums1[k++]=nums2[j++]; } } while(i<m) nums1[k++]=helper[i++]; while(j<n) nums1[k++]=nums2[j++]; System.out.println(Arrays.toString(nums1)); } public static void main(String[] args) { int nums1[] = {1,2,3,0,0,0}; int nums2[] = {2,5,6}; int m = 3, n = 3; merge(nums1, m, nums2, n) ; } }若在上面基础上增加不该比那原数组元素的相对顺序，该如何解决呢？ 这里使用双指针逆向扫描：
package 分治思想及快排双指针分区的应用; import java.util.Arrays; /** * @author JohnnyLin * @version Creation Time：2020年10月6日 下午3:55:11 * * https://leetcode-cn.com/problems/sorted-merge-lcci/ */ public class 合并排序的数组_逆向双指针 { //两个指针a,b分别从后往前扫描两个数组 p指针填充A数组 public static void merge(int[] A, int m, int[] B, int n) { if(m==0&&n!=0){//A中没有元素 B中右元素 A=Arrays.copyOf(B,n); return; } if(A==null) { return; } int a=m-1,b=n-1,p=m+n-1; while(a>=0&&b>=0) {//同时不为0 A[p--]=A[a]>=B[b]?A[a--]:B[b--]; // System.out.println(p+" "+a+" "+b); } //a,b while(a>=0) A[p--]=A[a--]; while(b>=0) A[p--]=B[b--]; System.out.println(Arrays.toString(A)); } public static void main(String[] args) { int nums1[] = {2,0}; int nums2[] = {1}; int m = 1, n = 1; merge(nums1, m, nums2, n) ; //int A[]={};//A==null false，A.length==0 true //int A[]={0};//A==null false，A.length==1 true } }