Skip to content

Instantly share code, notes, and snippets.

@pirate-kiiiing

pirate-kiiiing/FindKthLargest.java Secret

Last active October 8, 2022 09:42
Download ZIP

Revisions

  1. pirate-kiiiing revised this gist Oct 8, 2022. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions FindKthLargest.java
    View file
    Original file line number Diff line number Diff line change
    @@ -2,12 +2,12 @@ public int findKthLargest(int[] nums, int k) {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    private int quickSelect(int[] nums, int l, int r, int k) {
    int p = partition(nums, l, r, k);
    int p = partition(nums, l, r);
    if (p < k) return quickSelect(nums, p + 1, r, k);
    if (p > k) return quickSelect(nums, l, p - 1, k);
    return nums[p];
    }
    private int partition(int[] nums, int l, int r, int k) {
    private int partition(int[] nums, int l, int r) {
    int pivot = nums[r];
    int p = r;
    for (int i = l; i < p; i++) {
  2. pirate-kiiiing revised this gist Oct 8, 2022. No changes.
  3. pirate-kiiiing renamed this gist Oct 6, 2022. 1 changed file with 0 additions and 0 deletions.
    0 QuickSelect.java → FindKthLargest.java
    View file
    File renamed without changes.
  4. pirate-kiiiing revised this gist Oct 6, 2022. 1 changed file with 4 additions and 4 deletions.
    8 changes: 4 additions & 4 deletions QuickSelect.java
    View file
    Original file line number Diff line number Diff line change
    @@ -1,10 +1,10 @@
    public int findKthLargest(int[] nums, int k) {
    return qselect(nums, 0, nums.length - 1, nums.length - k);
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    private int qselect(int[] nums, int l, int r, int k) {
    private int quickSelect(int[] nums, int l, int r, int k) {
    int p = partition(nums, l, r, k);
    if (p < k) return qselect(nums, p + 1, r, k);
    if (p > k) return qselect(nums, l, p - 1, k);
    if (p < k) return quickSelect(nums, p + 1, r, k);
    if (p > k) return quickSelect(nums, l, p - 1, k);
    return nums[p];
    }
    private int partition(int[] nums, int l, int r, int k) {
  5. pirate-kiiiing created this gist Oct 6, 2022.
    27 changes: 27 additions & 0 deletions QuickSelect.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,27 @@
    public int findKthLargest(int[] nums, int k) {
    return qselect(nums, 0, nums.length - 1, nums.length - k);
    }
    private int qselect(int[] nums, int l, int r, int k) {
    int p = partition(nums, l, r, k);
    if (p < k) return qselect(nums, p + 1, r, k);
    if (p > k) return qselect(nums, l, p - 1, k);
    return nums[p];
    }
    private int partition(int[] nums, int l, int r, int k) {
    int pivot = nums[r];
    int p = r;
    for (int i = l; i < p; i++) {
    if (nums[i] > pivot) {
    swap(nums, i, p - 1);
    swap(nums, p, p - 1);
    i--;
    p--;
    }
    }
    return p;
    }
    private void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
    }