[LC 215]. Kth Largest Element in an Array

记录一个完整的quick selection的写法

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        shuffle(nums);
        int p = quickSelection(nums, 0, n - 1, n - k + 1);
        return nums[p];
    }

    private void shuffle(int[] a) {
        Random random = new Random();
        for (int i = 1; i < a.length; i++) {
            int r = random.nextInt(i+1);
            swap(a, i, r);
        }
    }

    private int quickSelection(int[] a, int lo, int hi, int k) {
        int i = lo, j = hi, pivot = a[hi];
        while (i < j) {             if (a[i++] > pivot) swap(a, --i, --j);
        }
        swap(a, i, hi); 

        int m = i - lo + 1;
        if (m == k) return i;
        else if (m < k) return quickSelection(a, i + 1, hi, k - m);
        else            return quickSelection(a, lo, i - 1, k);
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

–Random shuffle整个array会让整个algorithm的平均时间变成O(n),之前最好是O(n), 最差是O(n^2)
–Quick selection本质是一部分的quick sort。在整个array范围内,取一个pivot(shuffle之后相当于随机取一个数作为pivot),把所有小于pivot的数放在它左边,大于的放在它右边,然后看pivot是第几个。如果pivot在第k个之前,那么继续在右边subarray上做同样的事情,如果pivot在第k个之后,那么继续在左边subarray上作同样的事情。

其中一些细节:

while (i < j) {     
    if (a[i++] > pivot) swap(a, --i, --j);
}

这是不断把大于pivot的数丢到最右边

swap(a, i, hi);

这是把pivot放到左右两部分中间(pivot和头一个大于pivot的数交换)

int m = i - lo + 1;

这是count the numbers that are <= pivot from lo

if (m == k) return i;
else if (m < k) return quickSelection(a, i + 1, hi, k – m);
else return quickSelection(a, lo, i – 1, k);

这里的k已经不是最初的k了,是在当前的(lo, hi)范围内需要找到的第k个。如果找到的pivot超过了第k个,那么在pivot的左边重新找第k个,如果找到的pivot还没到第k个,那么在pivot的右边,再找k-m个<= pivot的数。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s