- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
数组 sort 排序
constgetLeastNumbers=function(arr,k){returnarr.sort((a,b)=>a-b).slice(0,k)}
- 时间复杂度: O(nlogn)
- 空间复杂度: O(logn)
大顶堆
我们可以借助大顶堆，因为大顶堆的节点值都大于等于其左右子节点的值，并且堆顶的元素最大。
JavaScript 需要自己构建大顶堆，可以参考：https://juejin.cn/post/6932482325159067656
- 从数组中取出前 k 个数，构建一个大顶堆
- 从 k 开始遍历数组，每个元素都与堆顶元素比较，如果比堆顶元素小，则将其替换为堆顶元素，然后再堆化成一个大顶堆
- 这样遍历完成后，堆中的数据就是前 K 小的元素了
constgetLeastNumbers=function(arr,k){constheap=[,]leti=0while(i<k){heap.push(arr[i++])}buildHeap(heap,k)for(leti=k;i<arr.length;i++){if(heap[1]>arr[i]){heap[1]=arr[i]heapify(heap,k,1)}}heap.shift()returnheap}constbuildHeap=(arr,k)=>{if(k===1)returnfor(leti=Math.floor(k/2);i>=1;i--){heapify(arr,k,i)}}constheapify=(arr,k,i)=>{while(true){letmaxIndex=iif(2*i<=k&&arr[i]<arr[2*i]){maxIndex=2*i}if(2*i+1<=k&&arr[maxIndex]<arr[2*i+1]){maxIndex=2*i+1}if(maxIndex!==i){swap(arr,i,maxIndex)i=maxIndex}else{break}}}constswap=(arr,i,j)=>{lettemp=arr[i]arr[i]=arr[j]arr[j]=temp}
- 时间复杂度: O(nlogk)
- 空间复杂度: O(k)
计数排序
数组范围有限时，要想到用计数排序。
用一个新的数组统计每个数字出现的次数，然后控制输出前 k 个即可。
constgetLeastNumbers=function(arr,k){constcountingSort=(arr,maxValue,k)=>{constlen=arr.lengthconstbucket=newArray(maxValue+1)constbucketLen=maxValue+1letsortedIndex=0for(leti=0;i<len;i++){if(!bucket[arr[i]]){bucket[arr[i]]=0}bucket[arr[i]]++}constres=[]for(letj=0;j<bucketLen;j++){while(bucket[j]-->0&&sortedIndex<k){res[sortedIndex++]=j}if(sortedIndex===k){break}}returnres}returncountingSort(arr,10000,k)}
- 时间复杂度: O(n + m)，m 表示数据范围
- 空间复杂度: O(k + m)