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

leetcode,215,Kth Largest Element in an Array,给定一个包括若干元素的数组以及一个k，要求在数组中找出第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```