查找数组arr中第k大的奇数,如果不存在则返回0. (arr[i] > 0 (i>=0))
计算出时间复杂度(注意代码注释,不能使用自带的排序函数)
格式:
public int findKth(int[] arr, int k){
//代码
}
计算出时间复杂度(注意代码注释,不能使用自带的排序函数)
格式:
public int findKth(int[] arr, int k){
//代码
}
调试欢乐多
定义一个长度为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