Kth Largest Element in an Array

Leetcode

題意:

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,

Given [3,2,1,5,6,4] and k = 2, return 5.

Note:

You may assume k is always valid, 1 ≦ k ≦ array's length.

解題思路:

updated on 2016.1.18

用heap來作更簡單,但得看面試官給不給用。

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> res = new PriorityQueue<Integer>();

        for (int i = 0; i < nums.length; i++) {
            if (res.size() < k) {
                res.offer(nums[i]);
            } else if (res.peek() < nums[i]) {
                res.poll();
                res.offer(nums[i]);
            }
        }

        return res.poll();
    }
}

使用 quick select來達到 O(N)的時間複雜度,不斷的用pivot把陣列切兩半,其程式碼如下:

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if (k > len) {
            return 0;
        }
        return quickSelect(nums, 0, len - 1, len - k);
    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        int pivot = right;
        int num = nums[pivot];
        int low = left;
        int high = right;

        while (low < high) {
            //從low開始找到一個比pivot大的數
            while (low < high && nums[low] < num) {
                low++;
            }
            // 從high開始找到一個比pivot小的數
            // 設>=表示忽略pivot
            while (low < high && nums[high] >= num) {
                high--;
            }
            swap(nums, low, high);
        }
        // 交換pivot與目前high指向的位置
        // 因pivot選最後一位,因此必須選一個比pivot大的數來作交換
        // 此時low指針已high指針已重疊,即該數大於pivot,直接作交換
        swap(nums, low, pivot);

        if (low == k) {
            return nums[low];
        }
        if (low > k) {
            return quickSelect(nums, left, low - 1, k);
        } else {
            //因為陣列的index都還在,所以直接丟k進去即可
            return quickSelect(nums, low + 1, right, k);
        }

    }

    private void swap(int[] nums, int idxA, int idxB) {
        int temp = nums[idxA];
        nums[idxA] = nums[idxB];
        nums[idxB] = temp;
    }
}

updated 2015.12.1

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || k == 0) {
            return 0;
        }
        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] nums, int start, int end, int k) {
        int pivot = end;
        int left = start;
        int right = end - 1;

        while (left <= right) {
            if (nums[left] > nums[pivot]) {
                swap(nums, left, right);
                right--;
            } else {
                left++;
            }
        }

        swap(nums, left, pivot);
        int rank = nums.length - left;
        if (rank == k) {
            return nums[left];
        }
        if (rank > k) {
            return quickSelect(nums, left + 1, end, k);
        } else {
            return quickSelect(nums, start, left - 1, k);
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

還可以用heap,但面試官可能要你實作priority queue。


public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();

        for (int i = 0; i < nums.length; i++) {
            q.offer(nums[i]);
            if (q.size() > k) {
                q.poll();
            }
        }

        return q.poll();
    }
}

results matching ""

    No results matching ""