不排序，怎么找到第 K 大的数？

数组中的第K个最大元素题目描述只有 20001 种可能的取值一批一批跳过直到找到目标名次代码里的变量表示什么C 实现C main调用C 实现C main调用复杂度与易错点这套思路还能用在哪题目215. 数组中的第K个最大元素标签数组 · 计数 · 值域映射 · LeetCode 热题 100题目描述给定整数数组nums和整数k返回数组中第k大的元素。也就是把数组从大到小排列后排在第k个位置的那个数。重复数字也要分别占位置。比如[5,5,4]的第2大是5不能先去重。题目只需要返回一个数不需要返回前k个数也不需要返回它的下标。输入nums [3,2,1,5,6,4]k 2 输出5 输入nums [3,2,3,1,2,4,5,5,6]k 4 输出4第二个例子按从大到小排列是[6,5,5,4,3,3,2,2,1]第4个数为4。数据范围1 k nums.length 10^5-10^4 nums[i] 10^4。题目要求设计线性时间O(n)的算法n是数组长度。只有 20001 种可能的取值直接排序再取答案很直观但一般的比较排序需要O(n log n)时间。再看数据范围每个数都在-1000010000之间一共只有20001 个可能的整数。我们可以准备一个计数数组记下每个数出现了几次。接着从大数往小数看。既然知道某个数有几个就能一次跳过这一批名次不必真的把所有元素重新排列。数组下标不能为负数所以给数值统一加上10000原数值计数数组下标-1000000100001000020000于是counts[value 10000]记录数字value出现了几次。例如-3对应下标9997counts[9997] 2表示数组里有两个-3。下标越大对应的数也越大。因此从计数数组的末尾向前扫描就是从大数往小数查找。一批一批跳过直到找到目标名次用第二个例子走一遍nums [3,2,3,1,2,4,5,5,6] k 4统计后从大到小的数字及数量为数字 6 5 4 3 2 1 个数 1 2 1 2 2 1令remaining k表示跳过前面的大数后还要找剩下元素中的第几大。当前数字出现次数remaining的变化61要找第 4 大跳过这 1 个剩余名次变成352要找第 3 大跳过这 2 个剩余名次变成141要找第 1 大正好落在这一批返回4表格省略了未出现的数字。代码也会经过它们但次数为0减去0不会改变剩余名次。判断规则只有两条remaining counts[index]这一批已经包含目标位置返回当前数字。否则跳过这一批让remaining - counts[index]继续看更小的数。为什么用小于等于如果当前有两个5而剩余名次是1或2答案都应该是5。这也正是重复元素不能去重的原因。每次扫描时更大的数字都已处理remaining始终保存剩下元素中的目标名次。因此一旦目标名次落入当前这批相同数字它们的数值就是答案。代码里的变量表示什么变量或表达式含义nums、k原数组和要找的名次k从1开始OFFSET偏移量10000把负数也映射到合法下标RANGE计数数组长度20001包含值域两端counts[index]数值index - OFFSET在原数组中出现的次数value、nums[i]C、C 统计时正在处理的一个原数组元素index从大到小扫描计数数组的下标不是原数组的下标remaining跳过更大的元素后剩下元素中的目标名次初始为knumsSizeC 版本中原数组的元素个数对应n统计时给数值加上OFFSET返回答案时给下标减去OFFSET。例如找到下标10004返回的数值就是4。C 实现#includevectorclassSolution{public:intfindKthLargest(conststd::vectorintnums,intk){enum{OFFSET10000,RANGE20001};intcounts[RANGE]{0};for(intvalue:nums){counts[valueOFFSET];}intremainingk;for(intindexRANGE-1;index0;--index){if(remainingcounts[index]){returnindex-OFFSET;}remaining-counts[index];}return0;// 题目保证 1 k nums.size()不会走到这里。}};C main调用#includecerrno#includecstdlib#includeiostream#includesolution.cppstructTestCase{constchar*name;std::vectorintnums;intk;intexpected;};staticboolrunCase(constTestCasetest,intnumber){std::vectorintnumstest.nums;Solution solution;intactualsolution.findKthLargest(nums,test.k);boolunchangednumstest.nums;boolpassedactualtest.expectedunchanged;std::coutCase number (test.name)\n nums [;for(std::size_t i0;itest.nums.size();i){if(i!0)std::cout,;std::couttest.nums[i];}std::cout], k test.k\n expected test.expected, actual actual, input unchanged (unchanged?true:false) - (passed?PASS:FAIL)\n;returnpassed;}intmain(intargc,char*argv[]){// 在这里修改输入、k 和预期结果用例编号从 1 开始。conststd::vectorTestCasetests{{Example 1,{3,2,1,5,6,4},2,5},{Example 2,{3,2,3,1,2,4,5,5,6},4,4},{Duplicates count separately,{5,5,4},2,5},{All negative,{-1,-5,-3,-2},2,-2},{All equal,{7,7,7,7},3,7},{Largest element,{4,2,9,1},1,9},{Smallest element,{4,2,9,1},4,1},{Single zero,{0},1,0},{Upper value boundary,{-10000,10000,-10000,10000},2,10000},{Lower value boundary,{-10000,10000,-10000,10000},3,-10000},{Zero and mixed signs,{-1,0,0,1},2,0}};intcountstatic_castint(tests.size());intfirst0;intlastcount;if(argc2){std::cerrUsage: argv[0] [case-number: 1..count]\n;returnEXIT_FAILURE;}if(argc2){char*endnullptr;errno0;longnumberstd::strtol(argv[1],end,10);if(argv[1][0]0||argv[1][0]9||errnoERANGE||endargv[1]||*end!\0||number1||numbercount){std::cerrInvalid case number; choose 1..count.\n;returnEXIT_FAILURE;}firststatic_castint(number)-1;lastfirst1;}intpassed0;for(intifirst;ilast;i){if(runCase(tests[i],i1))passed;}intexecutedlast-first;std::coutSummary: passed/executed passed.\n;returnpassedexecuted?EXIT_SUCCESS:EXIT_FAILURE;}C 实现intfindKthLargest(int*nums,intnumsSize,intk){enum{OFFSET10000,RANGE20001};intcounts[RANGE]{0};for(inti0;inumsSize;i){counts[nums[i]OFFSET];}intremainingk;for(intindexRANGE-1;index0;--index){if(remainingcounts[index]){returnindex-OFFSET;}remaining-counts[index];}return0;// 题目保证 1 k numsSize不会走到这里。}C main调用#includeerrno.h#includestdbool.h#includestdio.h#includestdlib.h#includestring.h// 只编译 main.c这里会一并引入解题核心。#includesolution.ctypedefstruct{constchar*name;constint*nums;intnumsSize;intk;intexpected;}TestCase;staticboolrunCase(constTestCase*test,intnumber){printf(Case %d (%s)\n nums [,number,test-name);for(inti0;itest-numsSize;i){if(i!0)printf(,);printf(%d,test-nums[i]);}printf(], k %d\n,test-k);size_tbytes(size_t)test-numsSize*sizeof(int);int*numsmalloc(bytes);if(numsNULL){printf( expected %d, actual allocation failed - FAIL\n,test-expected);returnfalse;}memcpy(nums,test-nums,bytes);intactualfindKthLargest(nums,test-numsSize,test-k);bool unchangedmemcmp(nums,test-nums,bytes)0;bool passedactualtest-expectedunchanged;printf( expected %d, actual %d, input unchanged %s - %s\n,test-expected,actual,unchanged?true:false,passed?PASS:FAIL);free(nums);returnpassed;}intmain(intargc,char*argv[]){// 在这里修改输入、k 和预期结果修改数组后同步调整 numsSize。constTestCase tests[]{{Example 1,(constint[]){3,2,1,5,6,4},6,2,5},{Example 2,(constint[]){3,2,3,1,2,4,5,5,6},9,4,4},{Duplicates count separately,(constint[]){5,5,4},3,2,5},{All negative,(constint[]){-1,-5,-3,-2},4,2,-2},{All equal,(constint[]){7,7,7,7},4,3,7},{Largest element,(constint[]){4,2,9,1},4,1,9},{Smallest element,(constint[]){4,2,9,1},4,4,1},{Single zero,(constint[]){0},1,1,0},{Upper value boundary,(constint[]){-10000,10000,-10000,10000},4,2,10000},{Lower value boundary,(constint[]){-10000,10000,-10000,10000},4,3,-10000},{Zero and mixed signs,(constint[]){-1,0,0,1},4,2,0}};intcount(int)(sizeof(tests)/sizeof(tests[0]));intfirst0;intlastcount;if(argc2){fprintf(stderr,Usage: %s [case-number: 1..%d]\n,argv[0],count);returnEXIT_FAILURE;}if(argc2){char*endNULL;errno0;longnumberstrtol(argv[1],end,10);if(argv[1][0]0||argv[1][0]9||errnoERANGE||endargv[1]||*end!\0||number1||numbercount){fprintf(stderr,Invalid case number; choose 1..%d.\n,count);returnEXIT_FAILURE;}first(int)number-1;lastfirst1;}intpassed0;for(intifirst;ilast;i){if(runCase(tests[i],i1))passed;}intexecutedlast-first;printf(Summary: %d/%d passed.\n,passed,executed);returnpassedexecuted?EXIT_SUCCESS:EXIT_FAILURE;}两份代码都保留原数组的内容。最后的return 0只用于补全函数返回路径题目保证k有效正常情况下会在循环中找到答案。复杂度与易错点设数组长度为n可能的整数取值数量为U本题U 20001。时间复杂度O(n U)。初始化计数数组、统计全部元素再倒序扫描值域。额外空间O(U)。用于保存每个数的出现次数。本题的U固定因此随n增长时间是线性的可以视为O(n)空间相对n固定但实际仍需要 20001 个计数位置。需要留意三个地方不去重。一个数出现几次就占几个排序位置。倒序扫描并还原数值。第k大要从大的数开始找最后返回index - OFFSET。值域长度要包含两端。10000 - (-10000) 1 20001不能少掉最后一个位置。这种计数法依赖较小的整数值域。如果数字范围扩大到很大或者改为任意小数就不适合照搬这个计数数组。这套思路还能用在哪例如一批成绩都是0100的整数想找第k高的成绩。只需用 101 个位置统计各分数的人数再从高分往低分累计同分成绩也各占一个位置不做去重。这里的关键是按数值大小找名次出现次数只负责告诉我们这一批占几个位置。这与 347. 前 K 个高频元素 不同。比如[9,1,1,1]中第1大是9出现最多的却是1。两题都统计次数但排序依据不同不能把“数值大”和“出现多”混为一谈。