思路一:
利用快排算法先将数组排序,然后在定位到第K个元素即可,算法复杂度为O(nlogn)
思路二:
利用快排和二分查找,先把数组分成两个部分,左边的比数轴pivot小,右边的比数轴pivot大。然后再比较pivot的位置和K的关系,如果比K大,那么第K个值就在pivot的左边,反之若比K小,则第K个值就在pivot的右边,若相等则直接返回。这种方法的复杂度要低一些。
代码如下:
int partition(int arr[], int low, int high) { int pivot = arr[low]; while(low < high) { while(low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; while(low < high && arr[low] <= pivot) low++; arr[high] = arr[low]; } arr[low] = pivot; return low; } int findKth(int arr[], int low, int high, int k) { int kth; if(low == high) kth = arr[low]; else { int pivot = arr[low]; int splitPoint = partition(arr, low, high); if(k-1 == splitPoint) //数组是从0开始的,所以比较时给K减了1 kth = pivot; else if(k-1 < splitPoint) kth = findKth(arr, low, splitPoint-1, k); else if(k-1 > splitPoint) kth = findKth(arr, splitPoint+1, high, k); } return kth; }