当前位置：首页 > article >正文

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

article 2025/2/9 2:15:45

使用快排实现寻找第K大元素

- 题目描述
- - 要求
  - 数据范围
- 示例
- - 示例1
  - 示例2
- 解题思路
- - 算法优势
- 代码实现
- 代码解析
- 复杂度分析

题目描述

有一个整数数组，请你根据快速排序的思路，找出数组中第 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

输入：

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

返回值：

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

解题思路

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

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

算法优势

不需要对整个数组进行排序，只需要部分排序
平均时间复杂度为O(n)，最坏情况下为O(n²)
空间复杂度为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
}