寻找第K大的数 C语言实现的一种方法

article/2025/9/30 15:09:03

描述

在一个数组中，找到第K 大的数值
一个数组，如：[3,2,1,5,6,4] ，输入 2，返回：5
也就是这个K的取值，是从 1 开始的，不超过数组的最大个数

解决思路

可以使用任意的排查函数，把这个数组进行排序，【从大到小排序】，第 1 个最大值，在 C语言的数组中，索引为【0】，第 K 最大值，索引为：【K - 1】

C语言实现

结合网络上找的 java 语言的实现方法，改为 C语言实现
使用Visual Studio 2022 编译与调试通过

/* Visual Studio 2022 Compile */
#define _CRT_SECURE_NO_WARNINGS/** Find Kth Largest Number*/#include <stdio.h>
#include <string.h>
#include <stdlib.h>static int array_in[] = { 3,2,1,5,6,4 };/* array dump : for test */
void array_dump(int *array, int begin, int end)
{printf("\n");for (int i = begin; i <= end; i++){printf("array[%d] = %d\n", i, array[i]);}printf("\n");
}int find_kth(int *array, int start, int end, int k)
{int low = start;int high = end;int temp = array[low];while (low < high){/* 将小于中数值的数移动到数组左边 */while ((low < high) && (array[high] >= temp)){high--;}array[low] = array[high];/* 将大于中数值的数移动到数组右边 */while ((low < high) && (array[low] <= temp)){low++;}array[high] = array[low];}array[high] = temp;if (end - low + 1 == k){return temp;}else if (end - low + 1 > k){return find_kth(array, low + 1, end, k);}else{return find_kth(array, start, low - 1, k - (end - low + 1));}
}int main(void)
{int k_len = 0; /* 数组的长度 */int k_pos = 0x00; /* K 的位置 */int k_value = 0x00; /*  */k_len = sizeof(array_in) / sizeof(int);printf("array input is:\n");array_dump(array_in, 0, k_len - 1);printf("array length = %d\n", k_len);while (1){printf("\nPlease input then K position: ");scanf("%d", &k_pos);if ((k_pos == 0) || (k_pos > k_len)){printf("The input K position must in [1, %d]!\n", k_len);continue;}k_value = find_kth(array_in, 0, k_len - 1, k_pos);printf("The [%d]th largest number = %d\r\n", k_pos, k_value);}return 0;
}