数组中第K大的数

题目描述

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

思路：快排 + 二分
用快速排序思想把数组按降序排列，第K大元素的下标就是 targetPos = K-1
（如果按升序排列数组，第K大元素的下标就是n - K，代码要稍微改动一下，但思想都一样，看哪个更顺手了）
每次partition后数组被分为三段：a[0...pivot-1], a[pivot], a[pivot + 1, end]
比较pivot 和 targetPos的大小，若相等则返回a[pivot];
若不相等（大小关系看代码），这时就可以排除数组的一半了，则递归调用quickSort排序数组的剩余目标位置

时间复杂度：每次排除一半的元素，partition比较加交换需要操作n次，则 n + n/2 + n/4 + ... + 1，这是公比为1/2的等比数列，
Sn = a1(1 - q^n)/ (1 - q)， 带入数字得2n
所以 时间复杂度为 O(n)

降序排列数组

import java.util.*;
//时间复杂度O(n)
//
public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        int targetPos = K - 1;
        return quickSort(a, 0, n-1, targetPos);
    }
    private int quickSort(int[] a, int start, int end, int pos) {
        int pivot = partition(a, start, end);
        if (pivot == pos)
            return a[pos];
        else if (pivot < pos) 
            return quickSort(a, pivot + 1, end, pos);
        else
            return quickSort(a, start, pivot - 1, pos);
    }
    private int partition(int[] a, int start, int end) {
        int pivot = end;
        int count = start;
        for (int i = start; i < end; i++) {
            if (a[i] > a[pivot]) {
                swap(a, i, count++);
                //count++;
            }
        }
        swap(a, count, pivot);
        return count;
    }
    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

升序排列数组

import java.util.*;

public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        int targetPos = n - K;
        return quickSort(a, 0 , n-1, targetPos);

    }
    private int quickSort(int[] a, int start, int end, int pos) {
        int pivot = partition(a, start, end);
        if (pivot == pos)
            return a[pos];
        else if (pivot < pos)
            return quickSort(a, pivot + 1, end, pos);
        else
            return quickSort(a, start, pivot - 1, pos);
    }
    private int partition(int[] a, int start, int end) {
        int pivot = end;
        int count = start;
        for (int i = start; i < end; i++) {
            if (a[i] < a[pivot]) {
                swap(a, i, count);
                count++;
            }
        }
        swap(a, count, pivot);
        return count;
    }
    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}