第k个元素

尽量高效率的在一个乱序的数组中找到第k个大小的元素

如k=1，则为找到数组中最小的元素

思路：

1.可以先将数组排序，找第几个元素则为对应下标减一，快排时间复杂度O（nlgn）

2.分治法思维：将数组元素分区，左边都比主元小，右边都比主元大；主元一定在顺序数组的位置上，在判断k与主元下标的大小，大：右侧递归查找；小：左侧递归查找；相等，则返回主元（递归出口）复杂度O(n)

（分区思路代码示例）

public static void main(String[] args) {

int[] a = {3,9,7,6,1,2};

    int k = selectK(a, 0, a.length - 1, 2);

    System.out.println(k);

}

/**

*

* @param arr

* @param p 起点

* @param r 终点

* @param k 第k个元素

* @return

*/

public static int selectK(int[] arr, int p, int r, int k) {

int q = partition(arr, p, r);

int qk = q-p+1;//主元是第qk个元素

if(qk == k) return arr[q];

else if(qk > k) return selectK(arr, p, q-1, k);//目标在主元左侧

else return selectK(arr, q + 1, r, k - qk);//注意：主元在目标右侧，转为求第 k - qk个

}

static int partition(int[] arr, int p, int r) {

int pivot = arr[p];//假设第一个元素为主元

int sp = p + 1;

int bigger = arr.length - 1;

while(sp <= bigger) {

if(arr[sp] <= pivot) {

sp++;

}else {

swap(arr, sp, bigger);

bigger--;

}

}

swap(arr, p, bigger);

return bigger;//返回主元位置

}

static void swap(int[] arr, int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}