2026-04-12:统计合格元素的数目。用go语言,给定一个长度为 n 的整数数组 nums,以及一个整数 k。 我们把数组中的某个元素记为“合格”,当且仅当:在数组中比它大的元素数量不少于 k 个

张开发
2026/4/12 7:56:26 15 分钟阅读

分享文章

2026-04-12:统计合格元素的数目。用go语言,给定一个长度为 n 的整数数组 nums,以及一个整数 k。 我们把数组中的某个元素记为“合格”,当且仅当:在数组中比它大的元素数量不少于 k 个
2026-04-12统计合格元素的数目。用go语言给定一个长度为 n 的整数数组 nums以及一个整数 k。我们把数组中的某个元素记为“合格”当且仅当在数组中比它大的元素数量不少于 k 个也就是严格大于该元素的数至少有 k 个。请统计并返回数组里所有“合格”元素的数量。1 n nums.length 100000。1 nums[i] 1000000000。0 k n。输入 nums [3,1,2], k 1。输出 2。解释元素 1 和 2 均有至少 k 1 个元素大于它们。没有元素比 3 更大。因此答案是 2。代码执行过程详细分步描述第一步处理特殊边界条件代码首先判断k是否等于 0题目中k1不满足k0跳过该分支这个分支的作用是如果k0所有元素都满足「严格大于它的数至少0个」直接返回数组总长度即可。第二步对数组进行升序排序代码调用排序函数对原数组升序排列原数组[3, 1, 2]排序后数组[1, 2, 3]排序的目的方便快速找到「第k大的元素」进而判断哪些元素是合格元素。第三步定位「第k大的元素」先计算数组长度n3第k大的元素在升序排序后的数组中位置是n-k索引从0开始代入计算n-k 3-1 2即排序后数组索引为2的元素排序数组[1,2,3]索引2的元素是3这就是第1大的元素。第四步统计「合格元素」的数量题目定义严格大于该元素的数至少有k个 → 该元素为合格元素。升序排序后所有小于「第k大元素」的数都满足「至少有k个元素比它大」代码通过查找函数统计排序数组中小于「第k大元素(3)」的元素个数排序数组[1,2,3]中小于3的元素是1、2总数量为2第五步返回结果并输出将统计的数量2作为结果返回最终输出结果为2与题目要求一致。时间复杂度与额外空间复杂度分析1. 总时间复杂度代码的核心操作分为两部分数组排序Go 语言内置的排序算法时间复杂度为O(n log n)n是数组长度查找元素个数sort.SearchInts是二分查找时间复杂度为O(log n)其他操作赋值、判断都是常数时间 O(1)。总时间复杂度由最高量级的操作决定因此✅总时间复杂度O(n log n)2. 总额外空间复杂度额外空间指除了输入数组本身外代码执行过程中额外开辟的内存空间。排序操作Go 语言的切片排序是原地排序仅使用常数级的临时变量不额外开辟数组空间代码中仅定义了n、result等几个变量占用空间与数组长度n无关✅总额外空间复杂度O(1)常数级空间总结执行核心流程判断k0→数组升序排序→找到第k大元素→统计小于该元素的数量→返回结果时间复杂度O(n log n)主要耗时在排序额外空间复杂度O(1)原地操作无额外大空间开销。Go完整代码如下packagemainimport(fmtslicessort)funccountElements(nums[]int,kint)int{n:len(nums)ifk0{returnn}slices.Sort(nums)returnsort.SearchInts(nums,nums[n-k])// 小于第 k 大的元素个数}funcmain(){nums:[]int{3,1,2}k:1result:countElements(nums,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-frombisectimportbisect_rightfromtypingimportListdefcount_elements(nums:List[int],k:int)-int:nlen(nums)ifk0:returnn nums.sort()# bisect_right returns the index where to insert to keep sorted order,# which gives the count of elements target# Here we want the number of elements the k-th largest element# The k-th largest element is at index n-ktargetnums[n-k]returnbisect_right(nums,target-1)defmain():nums[3,1,2]k1resultcount_elements(nums,k)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includealgorithmintcountElements(std::vectorintnums,intk){intnnums.size();if(k0){returnn;}std::sort(nums.begin(),nums.end());// Get the k-th largest elementintkth_largestnums[n-k];// Count elements strictly less than kth_largestintcount0;for(intnum:nums){if(numkth_largest){count;}else{break;// Since array is sorted, we can break early}}returncount;}intmain(){std::vectorintnums{3,1,2};intk1;intresultcountElements(nums,k);std::coutresultstd::endl;return0;}

更多文章