【leetcode】找出数组的第k大的数

用快排，原始的快排

def quick_sort(nums,l,r):
    if l<=r:return
    tmp = nums[0]
    while l<r:  
        while l<r and nums[r]>tmp:
            j-=1
        nums[j],nums[i]=nums[i],nums[j]
        while l<r and nums[i]<tmp:
            i+=1
        nums[i],nums[j]=nums[j],nums[i]
    nums[i]=tmp

    quick_sort(nums,0,i-1)
    quick_sort(nunms,i+1,len(nums)-1)

 在此基础上，

O（n）的算法思想借鉴了快排的思想：

对于快速排序，算法复杂度是O(N*logN)。而这个算法的算法复杂度是O(N)。为什么呢？

第一次交换，算法复杂度为O(N)，接下来的过程和快速排序不同，快速排序是要继续处理两边的数据，再合并，合并操作的算法复杂度是O(1)，于是总的算法复杂度是O(N*logN)（可以这么理解，每次交换用了N，一共logN次）。但是这里在确定枢纽元的相对位置（在K的左边或者右边）之后不用再对剩下的一半进行处理。也就是说第二次插入的算法复杂度不再是O(N)而是O(N/2)，这不还是一样吗？其实不一样，因为接下来的过程是1+1/2+1/4+........ < 2，换句话说就是一共是O(2N)的算法复杂度也就是O(N)的算法复杂度。

'''
找出数组的第k大的数：[6,7,8,9, 3, 2, 4, 8]第3大的数是4
'''
class Solution:
    def call(self, nums, k):
        if nums == None or len(nums) == 0:
            return -1
        result = self.qsort(nums, 0, len(nums) - 1, k)
        return result
 
    def qsort(self, nums, L, u, k):
        '''
        快排的一次快排操作函数
        :param nums: 
        :param L: 左边
        :param u: 右边
        :param k: 第k大
        :return: 
        '''
        if L >= u:
            return nums[u]
 
        m = L
        for i in range(L + 1, u + 1):  # u + 1保证遍历到u位置的值
            # 以nums[L]为基准，只要m右边的比它大就转到m左边
            if nums[i] > nums[L]:
                m += 1
                nums[m], nums[i] = nums[i], nums[m]
        # 此时，m左边的比nums[m]大，右边的比nums[m]小
        nums[m], nums[L] = nums[L], nums[m]
        # m左边有k-1个数时，第k大的数就是nums[m]
        if m + 1 == k:
            return nums[m]
        elif m + 1 > k:  # 左边大于k-1个数时，第k大在左边
            return self.qsort(nums, L, m - 1, k)
        else:  # 小于k时，第k大在右边
            return self.qsort(nums, m + 1, u, k)
 
 
s = Solution()
print(s.call([6, 7, 9, 3, 2, 4, 8], 4))
#第4大的是数字6
#6

参考了别人的。。。忘了出处?

最后

以上就是无心向日葵为你收集整理的【leetcode】找出数组的第k大的数的全部内容，希望文章能够帮你解决【leetcode】找出数组的第k大的数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。