每日一题——使用快排实现寻找第K大元素

题目描述

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a，同时给定它的大小n和要找的 k，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

要求

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

数据范围

• 0 ≤ n ≤ 1000
• 1 ≤ K ≤ n
• 数组中每个元素满足 0 ≤ val ≤ 10000000

示例

示例1

输入：

[1,3,5,2,2],5,3

返回值：

2

示例2

输入：

[10,10,9,9,8,7,5,6,4,3,4,2],12,3

返回值：

9

说明：去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9

解题思路

本题可以使用快速选择算法（Quick Select）来解决，这是一种基于快速排序思想的选择算法。其核心思想是：

1. 选择一个基准元素（pivot）
2. 将数组分区，使得：
   • 左边的元素都小于等于基准
   • 右边的元素都大于基准
3. 根据基准的位置判断：
   • 如果基准位置正好是我们要找的位置，返回该元素
   • 如果要找的位置在左边，则在左半部分继续查找
   • 如果要找的位置在右边，则在右半部分继续查找

算法优势

1. 不需要对整个数组进行排序，只需要部分排序
2. 平均时间复杂度为O(n)，最坏情况下为O(n²)
3. 空间复杂度为O(1)，只需要常数级别的额外空间

代码实现

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param a int整型一维数组
 * @param aLen int a数组长度
 * @param n int整型
 * @param K int整型
 * @return int整型
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 分区函数
int partition(int arr[], int left, int right) {
    int pivot = arr[right]; // 选择最后一个元素作为基准
    int i = left ;       // i 是小于等于基准的元素的最后一个位置
    for (int j = left; j <= right; j++) {
        if (arr[j] >= pivot) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
        }//有点类似于快慢指针，快指针用来遍历查找出不断地大于等于基准的元素，用慢指针来定位目前是小于基准元素的元素，一旦发现，立刻替换。直到最后把基准的元素换过去。
    }
    return i-1 ; // 返回基准的位置由于最后一个右元素一定替换，所以最后一定执行i++,所以要i-1；
}

// 快速选择函数//第K大
int quickSelect(int* arr, int left, int right, int k)
 {
    if (left == right) {
        return arr[left];
    }//排序全完成了
    int pivotIndex = partition(arr, left, right); // 执行分区操作，找到基准元素应该呆的位置坐标
    if (pivotIndex == k-1) {//要注意第k的元素对应的索引是pivotIndex-1
        return arr[pivotIndex]; // 找到第k大的元素
    } else if (k-1 < pivotIndex) {
        return quickSelect(arr, left, pivotIndex - 1, k); // 在左半部分继续查找
    } else {
        return quickSelect(arr, pivotIndex + 1, right,
                           k); // 在右半部分继续查找
    }
}
int findKth(int* a, int aLen, int n, int K ) {
    return quickSelect(a, 0, n - 1, K); //找到第经过选择排序后的a[n-k+1]，倒数第k个，也就是 write code here
}

代码解析

1. partition 函数：

   • 选择最后一个元素作为基准
   • 使用双指针法进行分区
   • 返回基准元素的最终位置

2. quickSelect 函数：

   • 递归实现快速选择算法
   • 根据基准位置决定在哪一侧继续查找
   • 当找到正确位置时返回结果

3. findKth 函数：

   • 入口函数，调用 quickSelect
   • 注意这里要找第K大，所以要转换为找第pivotIndex==K-1大

复杂度分析

1. 时间复杂度：

   • 平均情况：O(n)
   • 最坏情况：O(n²)
   • 最好情况：O(n)

2. 空间复杂度：

   • O(1)，只需要常数级别的额外空间
   • 递归调用栈的空间复杂度平均为O(logn)