查找数组arr中第k大的奇数,如果不存在则返回0. (arr[i] > 0  (i>=0))
计算出时间复杂度(注意代码注释,不能使用自带的排序函数)
格式:
public int findKth(int[] arr, int k){

//代码
}

解决方案 »

  1.   

    这种都是最基本的算法,给你个思路,代码就不写了
    定义一个长度为k的临时数组tmp
    遍历arr,arr[i] 分别与tmp[0,1...k]比较,如果大于tmp的元素,则把arr[i]插入tmp,插入位置后的元素依次往后挪(位置大于k的被自动丢弃),最后返回tmp[k]即可
    如果要求不能重复,则在插入的过程中多一步操作,就是如果tmp中不存在arr[i]才插入,否则不插入
      

  2.   

    简单写一个吧,不考虑重复的public class Sample {
        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