[leetcode题解]215.Kth Largest Element in an Array(数组中找第k大数)

leetcode,215,Kth Largest Element in an Array,给定一个包括若干元素的数组以及一个k,要求在数组中找出第k大的数。
通常的思路是排序,然后可以快速找到第k大的数,时间复杂度o(nlogn)。比较好的方法是借助快排的思想,一次轴分,可以以o(n)的时间复杂度找到第k大数。

c++代码:

class Solution {
public:
    //author:凌风技术站-iaccepted
    int findKthLargest(vector<int>& nums, int k) 
    {
        int n = nums.size();
        k = n - k;
        
        int m = findKthLargest(nums, 0, n - 1, k);
        return nums[m];
    }
    //快排中单侧递归找
    int findKthLargest(vector<int> &nums, int l, int r, int k)
    {
        int m = partition(nums, l, r);
        if (m < k)
        {
            return findKthLargest(nums, m + 1, r, k);
        }
        else if (m > k)
        {
            return findKthLargest(nums, l, m - 1, k);
        }
        return m;
    }
    //划分,快排中轴划分方法
    int partition(vector<int> &nums, int l, int r)
    {
        int p = l - 1;
        int x = nums[r];
        for (int i = l; i < r; ++i)
        {
            if (nums[i] <= x)
            {
                ++p;
                swap(nums[i], nums[p]);
            }
        }
        swap(nums[++p], nums[r]);
        return p;
    }
};

python代码:

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        :author: 凌风技术站-iaccepted
        """
        n = nums.__len__()
        m = self.findKth(nums, 0, n - 1, n - k)
        return nums[m]
        
    def findKth(self, nums, l, r, k):
        m = self.partion(nums, l, r)
        #print(nums, m)
        if m < k:
            return self.findKth(nums, m + 1, r, k)
        elif m > k:
            return self.findKth(nums, l, m - 1, k)
        else:
            return m
        
    def partion(self, nums, l, r):
        x = nums[r]
        p = l - 1
        while l < r:
            if nums[l] <= x:
                p += 1
                nums[l], nums[p] = nums[p], nums[l]
            l += 1
        nums[p + 1], nums[r] = nums[r], nums[p + 1]
        return p + 1

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]215.Kth Largest Element in an Array(数组中找第k大数)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/115.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注