查找数组arr中第k大的奇数,如果不存在则返回0. (arr[i] > 0 (i>=0))
计算出时间复杂度(注意代码注释,不能使用自带的排序函数)
格式:
public int findKth(int[] arr, int k){
//代码
}
计算出时间复杂度(注意代码注释,不能使用自带的排序函数)
格式:
public int findKth(int[] arr, int k){
//代码
}
解决方案 »
- 在开启tomcat出现了这个报错,是什么原因,求指导
- 请问有用过jdk1.4开发过发邮件系统的吗?
- 帮忙分析一下~~应该怎么解决~Struts2基础相关....
- 敏捷软件开发原则模式与实践一书的adapter模式问题
- 发一个极度菜鸟的问题
- spring异常的问题,请高手解决一下
- Hibernate设置关联,比如(many to one),是否完全可以无视数据库本身有没有外键一类的关联存在
- jsp中OUT.PRINT后加HTML出现的问题
- struts:登录判断是在Action中完成的,但是登录成功了如何设置session呢
- xsd验证xml的有效性出现类型无效的问题
- 有大神帮我解决一下这个小问题吗
- 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