标题:快速排序
以下代码可以从数组a[]中找出第k小的元素
它使用了类似于快速排序中的分治算法,期望时间复杂度是O(N)的,
请仔细阅读分析源码,填写划线部分缺失的内容
package 一八年省赛真题; import java.util.Random; public class Main { public static int quickSelect(int a[],int l,int r,int k) { Random rand = new Random(); int p = rand.nextInt(r-l+1) + l; int x = a[p]; int tmp = a[p]; a[p] = a[r]; a[r] = tmp; int i = l, j = r; while (i<j) { while (i<j&&a[i]<x) i++; if (i<j) { a[j] = a[i]; j--; } while (i<j&&a[j]>x) j--; if (i<j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return quickSelect(_______________); //填空 else return quickSelect(a, l, i - 1, k); } public static void main(String[] args) { int a[] = {1,4,2,8,5,7}; System.out.println(quickSelect(a, 0, 5, 4)); } }
注意:只提交划线部分缺少的代码,不要抄写任何已经存在的代码或符号。
解题思路
本题在求解的时候根据题意就应该采用快速排序中的分治法来进行思考,该方法的基本思想是:采用了一种分治的策略,将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
然后我们可以很显然的看到最后填空的部分是一个递归,那么一定是子问题。所以根据else后面的代码,就可以推出正确答案。
关于这几种常用排序的基本思路,大家可以看我的这篇文章:“用大白话和面试官扯“八大常用排序算法的基本思想””
答案源码:
package 一八年省赛真题; import java.util.Random; public class Year2018_Bt5 { public static int quickSelect(int a[],int l,int r,int k) { Random rand = new Random(); int p = rand.nextInt(r-l+1) + l; int x = a[p]; int tmp = a[p]; a[p] = a[r]; a[r] = tmp; int i = l, j = r; while (i<j) { while (i<j&&a[i]<x) i++; if (i<j) { a[j] = a[i]; j--; } while (i<j&&a[j]>x) j--; if (i<j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return quickSelect(a, i + 1, r, k - i + l - 1); //填空 else return quickSelect(a, l, i - 1, k); } public static void main(String[] args) { int a[] = {1,4,2,8,5,7}; //1,2,4,5,7,8 //输出5 System.out.println(quickSelect(a, 0, 5, 6)); } }
输出样例:
?
第二题 2021年4月4日 腾讯笔试编程题第二题 描述 给出一个有0-9的数字组成的字符...
当我们学习surface命令时,已经看到了三维作图的一些端倪。在matlab中我么可以调...
Coonamd 对象定义了将对数据源执行的命令,可以用于查询数据库表并返回一个记录...
常见信号介绍 SIGINT 2 CtrlC时OS送给前台进程组中每个进程 SIGABRT 6 调用abort...
本文介绍了JSP编程技术实现一个简单的购物车程序,具体如下: 1 问题描述 利用JS...
XML/HTML Code 复制内容到剪贴板 input id = username name = username type = t...
作者个人研发的在高并发场景下,提供的简单、稳定、可扩展的延迟消息队列框架,...
ASP.Net Core的跨域设置比较简单 官方都整合了 具体的参见微软官方文档: https:...
1.有时候,那些清晨时最坚强的人,正是那些夜里哭着哭着睡着的人。 2.总有一个...
由于工作所需,最近花时间研究了html转换为pdf的功能。html转换为pdf的关键技术...