查找数组arr中第k大的奇数,如果不存在则返回0. (arr[i] > 0 (i>=0))
计算出时间复杂度(注意代码注释,不能使用自带的排序函数)
格式:
public int findKth(int[] arr, int k){
//代码
}
计算出时间复杂度(注意代码注释,不能使用自带的排序函数)
格式:
public int findKth(int[] arr, int k){
//代码
}
解决方案 »
- 程序发布的问题!求助。分不够在加
- jsp乱码问题求解决
- 在glassfish上建的数据源,为什么initialcontext.lookup("java:comp/env/..");这个方法不成功?
- structs2的另一个问题?
- 关于resin服务器下开发jpa+struts2.0+spring+hibernate+dwr的数据库表的ORM配置问题
- html:link动态传值问题
- JAVA的思考
- 谁能告诉我下面的<metadata ></metadata>标签有何用?
- 请问j2ee1.4的启动命令是??
- 初学者问题,各位大虾指点!!!(在线等待)
- 有大神帮我解决一下这个小问题吗
- jenkins构建任务失败
定义一个长度为k的临时数组tmp
遍历arr,arr[i] 分别与tmp[0,1...k]比较,如果大于tmp的元素,则把arr[i]插入tmp,插入位置后的元素依次往后挪(位置大于k的被自动丢弃),最后返回tmp[k]即可
如果要求不能重复,则在插入的过程中多一步操作,就是如果tmp中不存在arr[i]才插入,否则不插入
public static void main(String[] args) {
try {
int[] a = {1,3,5,4,6,2};
int m = findKth(a, 3);
System.out.println(m);
} catch (Exception e) {
e.printStackTrace();
}
}
public static int findKth(int[] arr, int k){
if (k > arr.length) return 0;
int[] tmp = new int[k]; //定义一个k长的数组
tmp[0] = arr[0];
int j = 0;
for (int i=1; i<arr.length; i++) {
for (j=0; j<k; j++) {
if (arr[i] > tmp[j]) break; //如果arr[i]比tmp[0,1...k]大,则记录位置j
}
if (j < k) {//如果找到j,则插入元素
for (int m=k-1; m>j; m--) tmp[m] = tmp[m-1]; //j位置后的元素往后挪
tmp[j] = arr[i];
}
}
return tmp[k-1];
}
}时间复杂度,考虑最坏的情况,就是外层循环n遍,内层查找k遍,挪位k遍,也就是n*2k