第k大元素

题目描述

在数组中找到第k大的元素

思路

考虑快排的做法，每次对数组的第一个元素排序，排序后根据其位置将数组一分为二，再对左、右子数组重复之前的做法，其基本思想是分治。
为了找到第k大的元素，参考快排，我们对第一个元素排序后，对其进行判断，分三种情况：

• 该元素就是第k大的，直接输出
• 该元素小于第k大的，对该元素的右子数组递归，终止条件即找到第k大
• 该元素大于第k大的，对该元素的左子数组递归 ，终止条件即找到第k大

代码

public int kthLargestElement(int k, int[] nums) {
        return getK(nums, 0, nums.length-1, k);
    }
    
    private int getK(int[] nums, int start, int end, int k)
    {
        if(start >= end)    {return nums[start];}
        int tar = nums[start];
        int lo = start;
        int i = start+1;
        int j = end;
        while(i <= j){
            if(nums[i] > nums[lo]){
                swap(nums, i, lo);
                i++;
                lo++;
            }
            else if(nums[i] == nums[lo]) {i++;}
            else{
                swap(nums, i, j);
                j--;
            }
        }
        if(k < (lo+1))  {
            return getK(nums, start, lo-1, k);
        }
        else if(k > i)  {
            return getK(nums, i, end, k);
        }
        else    return tar;
    }
    
    private void swap(int[] nums, int i, int j)
    {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

考差点

• 快排
  • 快排涉及到将第一个元素排序，保证左边小于等于，右边大于等于。注意数组可能有重复元素。所以其做法应该是：
    另lo指向待排序元素，i=lo+1，j指向最后一个元素。
    排序过程中考虑三种情况：
    • 1、[i] < [lo]，交换i-lo，i++，lo++
      排序前：lo i . . . . . . j
      排序后：. lo i . . . . . j
    • 2、 [i] = [lo] ，i++
      排序前：lo i . . . . . . j
      排序后：lo . i . . . . . j
    • 3、 [i] > [lo]，交换i-j，j–
      排序前：lo i . . . . . . j
      排序后：lo i . . . . . j .