题目

以尽量高的效率求出一个乱序数组中按数值顺序的第k个元素值

解法1

以arr={10,9,8,7,6,5,4,3,2,1},k=4的情况举例:
先选择一个候选中值6，比它小的放在它的左边，比它大的放在它的右边，那么该候选中值的排名可以知道是6。那么第4个元素在左边。

再在左边选一个候选中值2，，比它小的放在它的左边，比它大的放在它的右边，arr={1,2,5,3,4,6,10,7,8,9}。候选中值的排名是2，那么第4个元素在它的右边。

java">package com.company;import com.company.util.ArrayUtil;import java.util.Arrays;public class Test21 {/*第k个元素的左边k-1个元素都比它小，右边的元素都比它大*/public static void main(String[] args) {int k=4;
//        int[] arr={4, 6, 7, 0, 6, 4, 1, 0, 0, 10};int[] arr = ArrayUtil.randomArray(0, 11, 10);System.out.println(Arrays.toString(arr));System.out.println(find(arr, 0, arr.length - 1, k));Arrays.sort(arr);System.out.println(Arrays.toString(arr));}public static int find(int[] arr,int left,int right,int k){/*if (left>right){return -1;}*/int mid=(left+right)/2;//排序arr[left] arr[mid] arr[right]可能右重复int maxIndex=left;int minIndex=left;if(arr[mid]<arr[minIndex]){minIndex=mid;}if(arr[right]<arr[minIndex]){minIndex=right;}if(arr[mid]>arr[maxIndex]){maxIndex=mid;}if(arr[right]>arr[maxIndex]){maxIndex=right;}int midIndex=(left+right+mid)-(maxIndex+minIndex);System.out.println(midIndex);ArrayUtil.swap(arr,midIndex,left);System.out.println(Arrays.toString(arr));int j=right;int i=0;for ( i = left+1; i <j ; i++) {if(arr[i]>arr[left]){while(j>i){if(arr[j]<=arr[left]){ArrayUtil.swap(arr,i,j);break;}j--;}}}ArrayUtil.swap(arr,left,i-1);System.out.println(Arrays.toString(arr));if(arr[j]<=arr[left]){ArrayUtil.swap(arr,left,j);}if(i==k){return arr[i-1];}else if(i<k){return find(arr,i,right,k);}else{return find(arr,left,i-2,k);}}
}

解法2

先排序，再找出第k个元素。代码略。