编程小白leetcode~数组第k个最大元素215(分治法)

题目描述

在未排序的数组中找到第 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;
   }
}

执行用时分布图

效率有所提高，但是还是不太满意。等找到更好的方法再来补充