题目描述
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素
示例
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
思路一
遍历元素使元素按照顺序排序，取第k个最大的元素。这样做简单但是时间复杂度比较大所以效果不是太好
int findKthLargest(int* nums, int numsSize, int k) {
int i,j,temp,flag;
temp = flag = 0;
for(i=0;i<numsSize;i++)
{
for(j=i;j<numsSize-1;j++)
{
if(nums[i]<nums[j+1])
{
temp = nums[j+1];
nums[j+1] = nums[i];
nums[i] = temp;
}
}
}
flag = nums[k-1];
return flag;
}
用时分布图表
思路2
使用Quicksort,在每次迭代过程中，选择一个标志元素，然后划分数组为两部分
(1) 一部分大于该元素
(2) 另一部分是小于该元素
假如以数组[3,2,1,5,4,6]为例，选择3作为标志元素p，把小于3的元素分为一部分，大于3的元素分为一部分。最终的结果是[5, 6, 4, 3, 1, 2],现在3在第四个位置是第4大的元素，所以说若找比第4小的元素，向右移动，否则向左移动
�������void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y =temp;
}
int partition(int* nums,int left,int right)
{
int pivot,l,r;
pivot = nums[left];
l = left+1;
r = right;
while(l <=r)
{
if(nums[l]<pivot && nums[r]>pivot)
swap(&nums[l++],&nums[r--]);
if(nums[l]>=pivot)
l++;
if(nums[r]<=pivot)
r--;
}
swap(&nums[left],&nums[r]);
return r;
}
int findKthLargest(int* nums, int numsSize, int k)
{
int left =0,right=numsSize-1;
int p;
while(1)
{//p即为第p大的元素
p = partition(nums, left, right);
if(p == k-1)//若p等于我们要求的那个数，直接输出
{
return nums[p];
}
if(p > k-1)//若p大于我们要求的那个数，就向左移动即修改右元素
right = p-1;
else//若p小于我们要求的那个数，就向右移动即修改左元素
left = p+1;
}
}
执行用时分布图
效率有所提高，但是还是不太满意。等找到更好的方法再来补充
