快排

215. 数组中的第K个最大元素

  • 时间复杂度：O(n)，如上文所述，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」。

  • 空间复杂度：O(logn)，递归使用栈空间的空间代价的期望为 O(\log n)O(logn)。

    1. class Solution {
    2.   public int quickFind(int[] nums, int l, int r, int k){
    3.       if(l >= r) return nums[k];
    4.       int i = l - 1, j = r + 1, x = nums[l + r >> 1];
    5.       while(i < j){
    6.           do{i++;} while(nums[i] > x);
    7.           do{j--;} while(nums[j] < x);
    8.           if(i < j){
    9.               int tmp = nums[i];
    10.               nums[i] = nums[j];
    11.               nums[j] = tmp;
    12.           }
    13.       }
    14.       if(k <= j) return quickFind(nums, l, j, k);
    15.       else return quickFind(nums, j + 1, r, k);
    16.   }
    17.   public int findKthLargest(int[] nums, int k) {
    18.       return quickFind(nums, 0, nums.length - 1, k - 1);
    19.   }
    20. }

    归并

    剑指 Offer 51. 数组中的逆序对

  • res += mid - i + 1; 左半边比j指向的数大的个数

  • [l …….mid][mid + 1……r]
  • Image 1.png
  • 时间复杂度：同归并排序 O(n_log_n)。
  • 空间复杂度：同归并排序O(n)，因为归并排序需要用到一个临时数组。
    class Solution {
  public int mergeSort(int[] nums, int l, int r){
      if(l >= r) return 0;
      int mid = l + r >> 1;
      int res = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);
      int[] tmp = new int[r - l + 1];
      int i = l, j = mid + 1, k = 0;
      while(i <= mid && j <= r){
          if(nums[i] <= nums[j]){
              tmp[k++] = nums[i++];
          }else{
              res += mid - i + 1;
              tmp[k++] = nums[j++];
          }
      }
      while(i <= mid) tmp[k++] = nums[i++];
      while(j <= r) tmp[k++] = nums[j++];
      int t = 0;
      for(i = l; i <= r; i++){
          nums[i] = tmp[t++];
      }
      return res;
  }
  public int reversePairs(int[] nums) {
      return mergeSort(nums, 0, nums.length - 1);
  }
}