[LeetCode] 215. Kth Largest Element in an Array

本文主要是介绍[LeetCode] 215. Kth Largest Element in an Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/kth-largest-element-in-an-array/description/

题目

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.

思路

三种方法

1.

先排序再索引。排序使用库函数。

2.

利用快速排序的每次排序会确定一个原始的位置的特性。

3.

交换排序，循环次数取决于k，但数量一大。交换的次数太多造成 超时。

code

################# 方法 一 ################class Solution:def findKthLargest(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""tmp = sorted(nums,reverse=True)return tmp[k-1]

################## 方法 二 ###############
def quickSelect(nums, lo, hi, k):lt = lort = hipivot = nums[rt]while lt<rt:while nums[lt]<= pivot and lt<rt:lt += 1while nums[rt] >= pivot and lt<rt:rt -= 1nums[lt],nums[rt] = nums[rt],nums[lt]nums[hi], nums[rt] = nums[rt], nums[hi]if rt == k:return kelif rt>k:return quickSelect(nums, lo, lt-1, k)else:return quickSelect(nums, lt+1,hi, k)class Solution:def findKthLargest(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""n = len(nums)p = quickSelect(nums, 0, n - 1, n - k)return nums[p]

################## 方法 三 ###############class Solution:def findKthLargest(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""n = len(nums)for i in range(k):for j in range(n -i -1):if nums[j]>nums[j+1]:nums[j],nums[j+1] = nums[j+1],nums[j]return nums[n-k]

这篇关于[LeetCode] 215. Kth Largest Element in an Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---