# LeetCode 215. 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

## 思路

• 这道题使用快速排序的分区部分，快速排序的每一次分区都随机将一个元素放置在了最终位置.
• 我们对原数组进行不断的分区，如果当前确定的元素在第k大元素的左边，我们就对当前元素右边的元素进行排序；如果当前元素在第k大元素的右边，我们就对当前元素左边的元素进行排序，直到找到第K的元素为止.

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-01-23 22:57:06
class Solution:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
left, right = 0, len(nums) - 1
#
pivot = self._quicksort(nums, left, right)
while pivot != k - 1:
# 如果当前确定的位置在k的左边，说明要求的元素应该在右边
if pivot < k - 1:
left = pivot + 1
# 如果当前确定的位置在k的右边，说明要求的元素应该在左边
elif pivot > k - 1:
right = pivot - 1
pivot = self._quicksort(nums, left, right)
return nums[pivot]
# 快速排序
def _quicksort(self, nums, left, right):
pivot, j = right, left
for i in range(left, right):
if nums[i] > nums[pivot]:
if j != i:
nums[i], nums[j] = nums[j], nums[i]
j += 1
nums[j], nums[pivot] = nums[pivot], nums[j]
# 返回当前已经确定元素的索引
return j

|
2月前
|
Java
java lab8--------7-2 sdut-JAVA-Insert Integer element into array lists
java lab8--------7-2 sdut-JAVA-Insert Integer element into array lists
15 0
|
10月前
Leetcode 230. Kth Smallest Element in a BST

59 1
|

LeetCode 410. Split Array Largest Sum

129 0
|
Python
LeetCode 378. Kth S Element in a Sorted Matrix

94 0
|

LeetCode 229. Majority Element II

79 0
|

LeetCode 162. Find Peak Element

92 0
|
Python
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or
447 0
|

LeetCode 169. 多数元素 Majority Element
LeetCode 169. 多数元素 Majority Element
84 0
|

LeetCode 961. N-Repeated Element in Size 2N Array
LeetCode 961. N-Repeated Element in Size 2N Array
182 0

2825 0

DDNS