[LeetCode] 215. Kth Largest Element in an Array 数组中第k大的元素

2018/03/06 16:01
阅读数 11

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.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

找出一个非排序数组中第k大的元素。

解法1:排序法。使用常规排序方法后找到数组中对应下标的值。

解法2:将数组内容存入一升序优先队列中,进行k-1次pop操作,那么队尾的元素就是第k大的数字。

解法3:最大堆MaxHeap。使用数组内容构建一个最大堆,通过每次pop出堆顶后继续维护堆的结构,直到满足一定的次数(最大堆k-1次,最小堆size-k次),堆顶的元素就是第k大的数字,实现的效果与优先队列相同。

解法4:Quick Select, 利用快排的partition函数思想,选定一个数组内的值作为pivot,将小于pivot的数字放到pivot右边,大于等于pivot的数字放到pivot左边。接着判断两边数字的数量,如果左边的数量小于k个,说明第k大的数字存在于pivot及pivot右边的区域之内,对右半区执行partition函数;如果右边的数量小于k个,说明第k大的数字在pivot和pivot左边的区域之内,对左半区执行partition函数。直到左半区刚好有k-1个数,那么第k大的数就已经找到了。

Java: Sort, T: O(nlogn) S: O(1)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Java: MaxHeap, T: O(nlogk) S: O(k)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> p = new PriorityQueue<Integer>();
        for(int i = 0 ; i < nums.length; i++){
            p.add(nums[i]);
            if(p.size()>k) p.poll();
        }
        return p.poll();
    }
}

Java: Quick select, T: Avg O(n) Worst O(n^2), S: O(1)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, k - 1, 0, nums.length - 1);
    }
    
    private int quickSelect(int[] arr, int k, int left, int right){
        int pivot = arr[(left + right) / 2];
        int orgL = left, orgR = right;
        while(left <= right){
            // 从右向左找到第一个小于枢纽值的数
            while(arr[left] > pivot){
                left ++;
            }
            // 从左向右找到第一个大于枢纽值的数
            while(arr[right] < pivot){
                right --;
            }
            // 将两个数互换
            if(left <= right){
                swap(arr, left, right);
                left ++;
                right --;
            }
        }
        // 最后退出的情况应该是右指针在左指针左边一格
        // 这时如果右指针还大于等于k,说明kth在左半边
        if(orgL < right && k <= right) return quickSelect(arr, k, orgL, right);
        // 这时如果左指针还小于等于k,说明kth在右半边
        if(left < orgR && k >= left) return quickSelect(arr, k, left, orgR);
        return arr[k];
    
    }
    
    private void swap(int[] arr, int idx1, int idx2){
        int tmp = arr[idx1] + arr[idx2];
        arr[idx1] = tmp - arr[idx1];
        arr[idx2] = tmp - arr[idx2];
    
    }
} 

Python: Sort

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer}
    def findKthLargest(self, nums, k):
        return sorted(nums, reverse=True)[k - 1]

Python: Max Heap

from heapq import *
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if not nums:
            return -1
        
        h = []
        for i in xrange(len(nums)):
            if len(h) < k:
                heappush(h, nums[i])
            else:
                if h[0] < nums[i]:
                    heappop(h)
                    heappush(h, nums[i])

        return h[0]

Python: Quick select

import random
class Solution:
    def findKthLargest(self, nums, k):
        pivot = random.choice(nums)
        nums1, nums2 = [], []
        for num in nums:
            if num > pivot:
                nums1.append(num)
            elif num < pivot:
                nums2.append(num)
        if k <= len(nums1):
            return self.findKthLargest(nums1, k)
        if k > len(nums) - len(nums2):
            return self.findKthLargest(nums2, k - (len(nums) - len(nums2)))
        return pivot

Python: Quick select

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer}
    def findKthLargest(self, nums, k):
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot_idx = randint(left, right)
            new_pivot_idx = self.PartitionAroundPivot(left, right, pivot_idx, nums)
            if new_pivot_idx == k - 1:
                return nums[new_pivot_idx]
            elif new_pivot_idx > k - 1:
                right = new_pivot_idx - 1
            else:  # new_pivot_idx < k - 1.
                left = new_pivot_idx + 1
        
    def PartitionAroundPivot(self, left, right, pivot_idx, nums):
        pivot_value = nums[pivot_idx]
        new_pivot_idx = left
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        for i in xrange(left, right):
            if nums[i] > pivot_value:
                nums[i], nums[new_pivot_idx] = nums[new_pivot_idx], nums[i]
                new_pivot_idx += 1
            
        nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
        return new_pivot_idx

C++: Sort

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

C++: Priority queque

class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            /** priority_queue<int, vector<int>, less<int>> q; **/
            priority_queue<int, vector<int>> q;
            int len=nums.size();
            for(int val:nums){
                q.push(val);
            }
            while(q.size() > len-k+1){
                q.pop();
            }
            return q.top();
        }
    };

 

C++: MaxHeap

class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            //max heap method
            //min heap method
            //order statistics
            make_heap(nums.begin(), nums.end());
            int result;
            for(int i=0; i<k; i++){
                result=nums.front();
                pop_heap(nums.begin(), nums.end());
                nums.pop_back();
            }
            return result;
        }
    };

C++: Quick sort, partition

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int high = nums.size();
        int low = 0;
        while (low < high) {
            int i = low;
            int j = high-1;
            int pivot = nums[low];
            while (i <= j) {
                while (i <= j && nums[i] >= pivot)
                    i++;
                while (i <= j && nums[j] < pivot)
                    j--;
                if (i < j)
                    swap(nums[i++],nums[j--]);
            }
            swap(nums[low],nums[j]);

            if (j == k-1)
                return nums[j];
            else if (j < k-1)
                low = j+1;
            else
                high = j;
        }
    }
};

  

All LeetCode Questions List 题目汇总

  

  

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部