求助Kth Largest Element in an Array

下面是我在网上找的能accept的代码.我想不通的是下面这段:

        else if (pivot + 1 > k)

        {

            return select(nums, k, left, pivot - 1);

        }

        else

        {

            return select(nums, k, pivot + 1, right);

        }

举例子,数组是[3, 2, 1, 5, 6, 4],

假设用3做partition, 那么数组变为

[5, 6, 4]  3 [2, 1]

当k = 3时,pivot + 1 > k,也就是说在[5, 6, 4] 找第3大的数,这个正确

但是,当k=5时,pivot + 1 < k, select(nums, k, pivot + 1, right);按照代码,就是要在[2, 1]里继续找第5大的数,我就很不明白了,不是应该在[2, 1]里继续找第k - pivot - 1 = 1大的数吗?为什么还是继续找第5大的数.

但是,代码在leetcode里却能跑过,而改成return select(nums, k - pivot - 1, pivot + 1, right);却报stack overflow...

===================

public class Solution

{

    public int findKthLargest(int[] nums, int k)

    {

        return select(nums, k, 0, nums.length - 1);

    }

    int partition(int[] data, int l, int r)

    {

        int left = l;

        int right = r;

        int pivot = data[left];

        while (left < right)

        {

            while (left < right && data[right] <= pivot)

            {

                right--;

            }

            

            data[left] = data[right];

            while (left < right && data[left] >= pivot)

            {

                left++;

            }

            data[right] = data[left];

        }

        data[left] = pivot;

        return left;

    }

    private int select(int[] nums, int k, int left, int right)

    {

        int pivot = partition(nums, left, right);

        if (pivot + 1 == k)

        {

            return nums[pivot];

        }

        else if (pivot + 1 > k)

        {

            return select(nums, k, left, pivot - 1);

        }

        else

        {

            return select(nums, k, pivot + 1, right);

        }

    }

}

===================

你看递归结束的条件， 肯定不是 k==1的时候结束， 估计是  lft == k

hot2346 发表于 2016-12-29 03:24
你看递归结束的条件， 肯定不是 k==1的时候结束， 估计是  lft == k

多谢指点..字数字数..

这个和在bst中找第k大的数是不一样的

它依旧是在原数组里找出第5大的数，但已经把范围缩小到了[2,1]，并不是说在新的数组里找出第k大的数