面試題 17.14. 最小K個(gè)數(shù)

設(shè)計(jì)一個(gè)算法，找出數(shù)組中最小的k個(gè)數(shù)。以任意順序返回這k個(gè)數(shù)均可。

示例：

輸入： arr = [1,3,5,7,2,4,6,8], k = 4
輸出： [1,2,3,4]
提示：

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

解題思路

通過快速選擇，我們可以將數(shù)組劃分成兩個(gè)區(qū)間A[l,i]，B[i+1,r],A區(qū)間的所有元素均小于B區(qū)間

• 如果k剛好就是A區(qū)間的長度的話，說明我們已經(jīng)找到了最小的k個(gè)數(shù)字
• 如果k大于A區(qū)間長度的話，說明我們要找的除了整個(gè)A區(qū)間以外，還有B區(qū)間的一部分元素
• 如果k小于A區(qū)間長度的話，說明我們需要找的數(shù)全部在A區(qū)間里面

代碼

class Solution {public int[] smallestK(int[] arr, int k) {int[] res=new int[k];int l=0,r=arr.length-1,w=k;while(l<r){int i=partition(arr,l,r);int n=i-l+1;if(n==k){break;}else if(n<k){l=i+1;k-=n;}else {r=i;}}System.arraycopy(arr,0,res,0,w);return res;}public int partition(int[] arr, int l,int r) {int t=arr[l];while(l<r){while(l<r&&arr[r]>=t)r--;arr[l]=arr[r];while(l<r&&arr[l]<=t)l++;arr[r]=arr[l];}arr[l]=t;return l;} }

總結(jié)

以上是生活随笔為你收集整理的面试题 17.14. 最小K个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。