第k个元素

标题

以尽量高的服从求出一个乱序数组中按数值顺序的第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个元素在它的右边。

1. package com.company;
3. import com.company.util.ArrayUtil;
5. import java.util.Arrays;
7. public class Test21 {
8.     /*第k个元素的左边k-1个元素都比它小，右边的元素都比它大*/
9.     public static void main(String[] args) {
10.         int k=4;
11. //        int[] arr={4, 6, 7, 0, 6, 4, 1, 0, 0, 10};
12.         int[] arr = ArrayUtil.randomArray(0, 11, 10);
13.         System.out.println(Arrays.toString(arr));
14.         System.out.println(find(arr, 0, arr.length - 1, k));
15.         Arrays.sort(arr);
16.         System.out.println(Arrays.toString(arr));
19.     }
20.     public static int find(int[] arr,int left,int right,int k){
21.         /*if (left>right){
22.             return -1;
23.         }*/
24.         int mid=(left+right)/2;
26.         //排序arr[left] arr[mid] arr[right]可能右重复
27.         int maxIndex=left;
28.         int minIndex=left;
29.         if(arr[mid]<arr[minIndex]){
30.             minIndex=mid;
31.         }
32.         if(arr[right]<arr[minIndex]){
33.             minIndex=right;
34.         }
36.         if(arr[mid]>arr[maxIndex]){
37.             maxIndex=mid;
38.         }
39.         if(arr[right]>arr[maxIndex]){
40.             maxIndex=right;
41.         }
42.         int midIndex=(left+right+mid)-(maxIndex+minIndex);
43.         System.out.println(midIndex);
45.         ArrayUtil.swap(arr,midIndex,left);
46.         System.out.println(Arrays.toString(arr));
48.         int j=right;
50.         int i=0;
51.         for ( i = left+1; i <j ; i++) {
53.             if(arr[i]>arr[left]){
55.                 while(j>i){
56.                     if(arr[j]<=arr[left]){
57.                         ArrayUtil.swap(arr,i,j);
58.                         break;
59.                     }
60.                     j--;
61.                 }
62.             }
63.         }
64.         ArrayUtil.swap(arr,left,i-1);
65.         System.out.println(Arrays.toString(arr));
66.         if(arr[j]<=arr[left]){
67.             ArrayUtil.swap(arr,left,j);
68.         }
71.         if(i==k){
72.             return arr[i-1];
73.         }else if(i<k){
74.             return find(arr,i,right,k);
75.         }else{
76.             return find(arr,left,i-2,k);
77.         }
78.     }
79. }

复制代码

解法2

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。