题目描述

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

我的解法

Beat 92.49%
快排的分治思想。随机选取一个pivot，小于的放左边，大于等于的放右边，返回pivot的位置：
- 如果pivot == k，则正好找到了第k小的元素
- 如果pivot > k，则第k小的元素存在于pivot左边
- 如果pivot < k，则第k小的元素存在于pivot右边
平均时间复杂度nlogn，最好n，最坏n²

我的解法多用了一个大小为n的数组，用于暂存数组。

class Solution {
  public int findKthLargest(int[] nums, int k) {
  	int len = nums.length;
  	int l = 0,r = nums.length - 1;
    	
  	while(true){
  		int nums_t_l = l,nums_t_r = r;
  		int[] nums_t = new int[nums.length];
    		
  		boolean ischanged_l = false,ischanged_r = false;
    		
  		for(int i = l;i <= r;i++){
  			if(nums[l] < nums[i]) {nums_t[nums_t_r--] = nums[i];ischanged_r = true;}
  			else {nums_t[nums_t_l++] = nums[i];ischanged_l = true;}
  		}
    		
    		
  		if(ischanged_l) nums_t_l--;
  		else if(ischanged_r) nums_t_r++;
    		
  		int t = nums_t[l];
  		nums_t[l] = nums_t[nums_t_l];
  		nums_t[nums_t_l] = t;
    		
  		nums = nums_t;
    		
  		if(nums_t_l == len - k)
  			return nums_t[nums_t_l];
  		else if(nums_t_l > len - k)
  			r = nums_t_l - 1;
  		else
  			l = nums_t_r + 1;
  	}
  }
}

简便解法1

思想和我的一样，只是分区的时候，实现和我不同，是《算法》第四版的思想，较好。

节约了大小为n的数组

public int findKthLargest(int[] nums, int k) {

      k = nums.length - k;
      int lo = 0;
      int hi = nums.length - 1;
      while (lo < hi) {
          final int j = partition(nums, lo, hi);
          if(j < k) {
              lo = j + 1;
          } else if (j > k) {
              hi = j - 1;
          } else {
              break;
          }
      }
      return nums[k];
  }

  private int partition(int[] a, int lo, int hi) {

      int i = lo;
      int j = hi + 1;
      while(true) {
          while(i < hi && less(a[++i], a[lo]));//巧妙
          while(j > lo && less(a[lo], a[--j]));//巧妙
          if(i >= j) {
              break;
          }
          exch(a, i, j);
      }
      exch(a, lo, j);//巧妙
      return j;
  }

  private void exch(int[] a, int i, int j) {
      final int tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
  }

  private boolean less(int v, int w) {
      return v < w;
  }

改进：在partition前将数组顺序打乱，保证不出现最坏情况。 ``` public int findKthLargest(int[] nums, int k) {

  shuffle(nums);
  k = nums.length - k;
  int lo = 0;
  int hi = nums.length - 1;
  while (lo < hi) {
      final int j = partition(nums, lo, hi);
      if(j < k) {
          lo = j + 1;
      } else if (j > k) {
          hi = j - 1;
      } else {
          break;
      }
  }
  return nums[k];   }

private void shuffle(int a[]) {

    final Random random = new Random();
    for(int ind = 1; ind < a.length; ind++) {
        final int r = random.nextInt(ind + 1);
        exch(a, ind, r);
    }
} ```

简便解法2

利用最小堆，维护一个容量为k的最小堆，在建完堆后将取堆内第k个数即可。

public int findKthLargest(int[] nums, int k) {

  final PriorityQueue<Integer> pq = new PriorityQueue<>();
  for(int val : nums) {
      pq.offer(val);

      if(pq.size() > k) {
          pq.poll();
      }
  }
  return pq.peek();
}