【LeetCode】第k大元素

题目

题目

方法一：快排优化

注意

• 随机化：快排如果实现得不好，在遇到特殊测试用例时，时间复杂度会变得很高，故注意随机选择切分元素（pivot）。
  最极端的是顺序数组与倒序数组。
• 双指针：使用双指针，将与pivot相等的元素。

代码

public class Solution {
  private static Random random = new Random(System.currentTimeMillis());

  public int findKthLargest(int[] nums, int k) {
    int len = nums.length;
    int left = 0;
    int right = len - 1;
    while (true) {
      int index = partition(nums, left, right); // pivot排定后的下标
      if(index == k) {
        return nums[index];
      }  else if (index < k) {
        left = index + 1; // 第K大元素在pivot右侧
      } else {
        right = index - 1; // 第K大元素在pivot左侧
      }
    }
   }

  public int partition(int[] nums, int left, int right) {
    // 在区间随机选择一个元素作为pivot
    if (right > left) {
      int randomIndex = left + random.nextInt(right - left + 1);
      swap(nums, left, randomIndex);
    }
    
    int pivot = nums[left];
    // 将等于 pivot 的元素分散到两边
    // [left, lp) <= pivot
    // (rp, right] >= pivot
    int lt = left + 1;
    int rp = right;
    while (true) {
      while (lp <= rp && nums[lp]< pivot)
        lp++;
      while (lp <= rp && bums[rp] > pivot) {
        rp--;
      }
      if (lp > rp)
        break;
      swap(nums, lp, rp);
      lp++;
      rp--;
    }
    swap(nums, left, rp);
    return rp;
  }
}

方法二：堆

使用堆的好处是，可以处理庞大的数据，即数据不用一下子存到内存中。并且比较操作可以交给堆内部完成，代码看起来封装性更好，语义更清晰。
java中有一个优先队列PriorityQueue用来实现堆，但这里选择自己手动建堆。

大顶堆

官方给的题解是建立一个大根堆，然后进行k - 1次删除操作后得到堆顶元素

class Solution {
  public int findKthLargest(int[] nums, int k) {
    int heapSize = nums.length;
    buildMaxHeap(nums, heapSize);
    for (int i = nums.length - 1; i >= nums.length - k + 1; i--) {
      swap(nums, 0 , i);
      heapSize--;
      maxHeapify(nums, 0, heapSize);
    }
    return nums[0]
  }

  public void buildMaxHeap(int[] nums, int heapSize) {
    // 建堆过程，从最后一个非叶子节点为根结点的子树开始，将其调整为大根堆，依次调整倒数第二个非叶子节点，倒数第三个......根结点。
    for (int i = heapSize / 2 - 1; i >= 0; i--) {
      maxHeapify(nums, i, heapSize);
    }
  }

  // 递归版
  public void maxHeapify(int[] nums, int i, int heapSize) {
    int left = i * 2 + 1; // 左孩子
    int right = i * 2 + 2; // 右孩子
    int largest = i; // 堆顶
    // 越界判断，并取孩子中较大的那个
    if (left < heapSize && nums[left] > nums[largest]) {
      largest = left;
    }
    if (right < heapSize && nums[right] > nums[largest]) {
      largest = right;
    }
    // 下沉
    if (largest != i) {
      swap(nums, i, largest);
      maxHeapify(nums, largest, heapSize);
    }
  }

  // 循环版
  public void maxHeapify(int[] nums, int i, int heapSize) {
    int temp = nums[i];
    for (int k = 2 * i + 1; k < heapSize; k = 2 * k + 1) {
      if (k + 1 < heapSize && nums[k] < nums[k + 1]) {
        // 当前孩子节点不是完全二叉树的最后一个节点
        // 且最大值在右孩子上，否则在左孩子上
        k++;
      }
      if (temp > nums[k]) {
        // 当前的temp就是最大值，以它为根结点的子树满足堆的性质，可以停止下沉
        break;
      }
      nums[i] = nums[k]
      i = k; // 定位停止下沉的位置
    }
    nums[i] = temp;
  }
}

小顶堆

可以只对前k个元素堆排序，将堆的大小维持在k，这样复杂度将与k相关。然后将后面的元素与堆顶元素进行比较，如果大于当前堆顶元素，则称为新的堆顶元素。这样前n - k小的元素就都从k大小的堆中移走了。

class Solution {
  public int findKthLargest(int[] nums, int k) {
    buildHeap(nums, k, nums.length);
    for (int i = k; i < nums.length; i++) {
      if (nums[i] > nums[0]) {
        swap(nums, i, 0);
        adjustHeap(nums, 0, k);
      }
    }
    return nums[0];
  }
    
  private static void buildHeap(int[] nums, int k, int length) {
    for (int i = length / 2 - 1; i >= 0; i--) {
      adjustHeap(nums, i, k);
    }
  }

  private static void adjustHeap(int[] nums, int i, int length) {
    int temp = nums[i];
    for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
      if (k + 1 < length && nums[k] > nums[k + 1]) {
        k ++;
      }
      if (temp < nums[k]) {
        break;
      }
      nums[i] = nums[k];
      i = k;
    }
  }
  nums[i] = temp;
}