algo/di-yi-zhan-da78c/shou-ba-sh-66994/kuai-su-pa-39aa2/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-66994/kuai-su-pa-39aa2/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 215. Kth L...

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/kuai-su-pa-39aa2/

[shiboys]

尴尬了，使用快速选择排序, 提交 leetcode，居然没有我之前写的简易的二叉堆效率高，附上我写的简易二叉堆：

class Solution {
    public int findKthLargest(int[] nums, int k) {
       if(k < 1 || k>nums.length) {
          return -1;
      }
      return kthLargestByHeap(nums,k);
    }

    // 使用的是二叉堆
    int kthLargestByHeap(int[] nums, int k) {
        for (int i = nums.length >>> 1; i >= 0; i--) {
                // heapify，建一个大顶堆
                    sink(nums, i, nums.length - 1);
                }
                int result = nums[0];
                for (int i = 0; i < k; i++) {
                  int size = nums.length - 1 - i;
                  result = delMax(nums, size);
                }
            return result;
    }
    
    public int delMax(int[] arr, int size) {
    int result = arr[0];
    swap(arr, 0, size);
    sink(arr, 0, size - 1);
    return result;
  }

  // 大顶堆规则，最大元素在最上面
  void sink(int[] arr, int k, int heapSize) {
    int left = k * 2 + 1;
    int right = left + 1;
    while (left <= heapSize) {
      int child = left;
      if (right <= heapSize && arr[right] > arr[left]) {
        child = right;
      }
      if (arr[k] >= arr[child]) {
        break;
      }
      swap(arr, k, child);
      k = child;
      left = k * 2 + 1;
      right = left + 1;
    }
  }

  void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

快速选择排序执行时间就要要 2 s，而使用大顶堆的时间是 20 ms ，居然有 100 倍的性能差距

[Vicky7777]

我leetcode提交快速选择，timeout。。。。

[lvyhnzhng]

我也超时了。。

[guohuiyuan]

快排还真超时了

[petercdcn]

快排其实是可以过40/41 个测试的。最后一个测试超时，其实可以理解。第41个测试里面是这样的“1,2,3,4,5,1,1,1,1,1,1,1,1,1,1,1,1......" 遇到了快排的O（n^2）情节。

快排我提交两次，一次超时，一次过了（4.6秒）。慢我觉是被最后一个测试拖了后腿。

二叉堆是小于一秒的解法，不知道为什么。。。

[SpumeXi]

按照文章的快速排序算法写了几遍，每次到边界点都弄不清。记得学数据结构的时候没这么复杂，翻出李春葆版的数据结构，交换数组元素那里写的更加简洁明了，这次终于写出来了。
private void sort(int[] nums,int left,int right) {
if (left > right) {
return;
}
int p = privot(nums, left, right);
sort(nums, left, p-1);
sort(nums, p+1, right);
}

private int privot(int[] nums,int left,int right) {
    int temp = nums[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= temp) {
            j--;
        }
        nums[i]=nums[j];
        while (i < j && nums[i] <= temp) {
            i++;
        }
        nums[j]=nums[i];
    }
    nums[i]=temp;
    return i;
}

[petercdcn]

这个写法很好，但是我不解的地方是，为什么必须要先查temp右边，再查左边？如果我把这两个while循环，调换位置，就出错了。。。试着把这个两组代码换个位置，就行不通了。我一开始写，是先查的左边，再查的右边。

        while (i < j && nums[j] >= temp) {
            j--;
        }
        nums[i]=nums[j];
       // 如果把两个while换位置的话，不能用？
        while (i < j && nums[i] <= temp) {
            i++;
        }
        nums[j]=nums[i];

[KSroido]

因为基准是第零个元素, 位于左侧, 如果基准是最后一个元素就可以先查左边了

[BruceWong12]

if (i >= j) {
    break;
}

这里break时nums[i] = nums[j] > pivot
后面直接交换

swap(nums[lo], nums[j]);

会不会变成 nums[lo] > nums[p]?

[Jeffery18-hub]

递归本来就是树形结构吧。

[syz6]

文中的 partition 算法在力扣提交超时，下面的 partition 算法通过力扣测试，用时 5 ms

class Solution {

    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int start = 0, end = nums.length - 1;
        Random random = new Random();
        while (start <= end) {
            int pivot = start + random.nextInt(end - start + 1);
            int[] equalRange = partition(nums, start, end, pivot);
            if (k < equalRange[0]) end = equalRange[0] - 1;
            else if (k > equalRange[1]) start = equalRange[1] + 1;
            else return nums[equalRange[0]];
        }

        return Integer.MIN_VALUE;
    }

    /**  
    @param pivot 枢轴元素的索引
    @return 长度为 2 的数组。另 a, b 表示返回数组的 0, 1 号元素，pivotValue 表示调用方法时的 nums[pivot]，则方法返回后 nums 格局如下：
    nums[start..a - 1] < pivotValue
    nums[a..b] = pivotValue
    nums[b + 1..end] > pivotValue
    */
    int[] partition(int[] nums, int start, int end, int pivot) {
        int pivotValue = nums[pivot];

        // 循环常态：
        // nums[start..i) < pivotValue
        // nums[i..j) = pivotValue
        // nums(k..end] > pivotValue
        int i = start, j = i, k = end;
        while (j <= k) {
            if (nums[j] < pivotValue) {
                if (i != j) swap(nums, i, j);
                i++;
                j++;
            } else if (nums[j] == pivotValue) {
                j++;
            } else {
                while (k > j && nums[k] > pivotValue) k--;
                if (j < k) swap(nums, j, k);
                k--;
            }
        }

        return new int[] {i, j - 1};
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

[Valor-H]

215. 数组中的第 K 个最大元素 【C++】

class Solution {
private:
    vector<int> data;
    int target;
    int res;
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        target = n - k;
        data.resize(n);
        for (int i = 0; i < n; ++i) {
            data[i] = nums[i];
        }
        quickSort(0, n - 1);
        return res;
    }

    void quickSort(int left, int right) {
        if (left > right) return;
        if (left == right) {
            if (left == target) {
                res = data[target];
                return;
            }
        }
        vector<int> p = part(left, right);
        if (p[0] + 1 <= target && p[1] - 1 >= target) {
            res = data[target];
            return;
        }
        quickSort(left, p[0]);
        quickSort(p[1], right);
    }

    vector<int> part(int left, int right) {
        int pivot_idx = rand() % (right - left + 1) + left;
        int pivot = data[pivot_idx];
        swap(left, pivot_idx);
        int curp = left + 1, leftp = left, rightp = right + 1;
        while (curp < rightp) {
            if (data[curp] < pivot) {
                leftp++;
                swap(curp, leftp);
                curp++;
            } else if (data[curp] > pivot) {
                rightp--;
                swap(curp, rightp);
            } else {
                curp++;
            }
        }
        swap(left, leftp);
        return {leftp - 1, rightp};
    }

    void swap(int a, int b) {
        int tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }
};

[KSroido]

提一个建议哥, 我看您好多文章就有种感觉, 整体都写得很不错, 但是就是有些算法的边界条件没那么准确, 看起来感觉思路不那么清晰
比如这里的partition函数, 里面的while的第一个结束条件就不可能是i<hi, 因为从j到hi这个范围已经被上一次的while循环确保了不存在小于的内容, 改进如下

static int partition(vector<int> &nums, int left, int right) {
        // 以 nums[left] 为基准数
        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= nums[left])
                j--; // 从右向左找首个小于基准数的元素
            while (i < j && nums[i] <= nums[left])
                i++;          // 从左向右找首个大于基准数的元素
            swap(nums[i], nums[j]); // 将基准数交换至两子数组的分界线

        }
        swap(nums[i], nums[left]); // 将基准数交换至两子数组的分界线
        return i;            // 返回基准数的索引
    }

以上代码摘自其他教材

[codezs09]

partition 的另一种思路，双指针，初始时左指针指向 p+1（pivot右手边第一个index）,右指针指向最末一个元素 hi。开始比较， 如果 nums[left] <= pivot， 则交换 nums[left] 和 pivot 的元素，这样小的值 nums[left]就来到了p左手；否则则交换 nums[left] 和nums[right], 将大于 pivot的元素放到末尾。
测试通过。

static int partition(vector<T> &nums, int lo, int hi) {
    int p = lo;
    T pivot = nums[p]; // pivot value
    // in-place, use dual pointers
    int left = lo + 1, right = hi;
    while (left <= right) {
      if (nums[left] <= pivot) {
        swap(nums, p, left);
        p = left;
        left++;
      } else {
        swap(nums, left, right);
        right--;
      }
    }
    return p;
  }

[codezs09]

Cons:

• 这样的思路相比原代码会 swap 更多次