寻找第K大的数(快速排序的应用)

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

http://blog.csdn.net/hymanxq/article/details/51026818

public class 寻找第K大的数 {

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        int[] a = { , , , ,  };

        System.out.println(findKth(a, a.length, ));

        /*

         * qsort(a, 0, a.length-1); for(int i:a){ System.out.print(i+" "); }

         */

    }

    public static int findKth(int[] a, int n, int K) {

        // write code here

        return qs(a, , a.length - , a.length - K); // 第K大数 的下标

    }

    static void qsort(int[] a, int left, int right) {

        if (left < right) {

            int p = partition(a, left, right);

            qsort(a, left, p - );

            qsort(a, p + , right);

        }

    }

    static int qs(int[] a, int left, int right, int k) {

        // if (left < right)

        {

            int p = partition(a, left, right);

            if (p == k) {

                return a[p];

            } else if (p > k)

                return qs(a, left, p - , k);

            else

                return qs(a, p + , right, k);

        }

    }

    static int partition(int[] a, int left, int right) {

        int p = a[left];

        while (left < right) {

            while (left < right && a[right] >= p) {

                right--;

            }

            if (left < right) {

                a[left++] = a[right];

            }

            while (left < right && a[left] <= p) {

                left++;

            }

            if (left < right) {

                a[right--] = a[left];

            }

        }

        a[left] = p;

        return left;

    }

}

巴特西

寻找第K大的数(快速排序的应用)

最新文章

热门文章