劍指 Offer 40. 最小的k個數（簡單）

思路：

方法一：java給的函數方法Arrays.sort

方法二：快速排序+二分

方法三：大根堆（前k小），預設是小根堆，是以要重寫

代碼：

方法一：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
		Arrays.sort(arr);
		int[] res=new int[k];
		for(int i=0;i<k;i++){
			res[i]=arr[i];
		}
		return res;
		
    }
}
           

方法二：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
		//先做一個判斷
		if(k>=arr.length){
			return arr;
		}
		return quickSort(arr,k,0,arr.length-1); 
	}
	
	private int[] quickSort(
			int[] arr,
			int k,
			int i,
			int j
	){
		int l=i,r=j;
		while(i<j){
			while(i<j&&arr[j]>=arr[l]) j--;
			while(i<j&&arr[i]<=arr[l]) i++;
			swap(arr,i,j);
		}
		swap(arr,i,l);
		
		if(k<i) quickSort(arr,k,l,i-1);
		if(k>i) quickSort(arr,k,i+1,r);
		
		return Arrays.copyOf(arr,k);
	}
	
	private void swap(int[] arr,int i,int j){
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
}
           

方法三：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 預設是小根堆，實作大根堆需要重寫一下比較器。
        Queue<Integer> queue = new PriorityQueue<>((v1, v2) -> v2 - v1);
        
		for(int i=0;i<k;i++){
			queue.offer(arr[i]);
		}
		
		for(int i=k;i<arr.length;i++){
			if(arr[i]<queue.peek()){
				queue.poll();
				queue.offer(arr[i]);
			}
		}
		
		
        // 傳回堆中的元素
        int[] res = new int[queue.size()];
		int i=0;
        while(!queue.isEmpty()){
			res[i++]=queue.poll();
		}
        return res;
    }
}
           

分解：

1）面試的時候最好不要使用Arrays.sort()快排方法

2）方法二：

i）找到比基準點（這裡是l）大的數arr[i]。和比基準點小的數arr[j]

将i和j調換位置

ii）當i>=j時，調換arr[i]和基準點的位置

iii）接下來進行遞歸周遊（也就是二分）

這裡加一個判斷，可以隻進行一邊的遞歸：

當k在i左邊，說明數量已經夠了，就遞歸左邊；當k在i右邊，表明前i個還不夠，要接着遞歸右邊

if(k<i) quickSort(arr,k,l,i-1);
if(k>i) quickSort(arr,k,i+1,r);
           

iv）最後取arr數組中的前k個元素

return Arrays.copyOf(arr,k);
           

3）方法三：

建立一個優先隊列，預設是升序（小根堆），是以要重寫比較器

先把前k個元素加進去，再把後面的元素與前面的k個元素比較

如果後面的元素比堆頂（最小）的值小，則替換掉堆頂的元素

複雜度分析：

方法一：Arrays.sort()

    時間複雜度：O（NlogN）快排的時間複雜度平均是O（NlogN）

    空間複雜度：O（N）快排的遞歸深度平均為O（logN），最差情況俠士O（N），也就是數組完全倒序的情況

方法二：快排+二分

    時間複雜度：O（N）由于此題舍去了不必要的遞歸，如果沒有社群，快排的時間複雜度是O（NlogN）

    空間複雜度：O（N）同上

方法三：大根堆（前k小）

    時間複雜度：O（NlogK） N是數組arr的長度。大根堆實時維護前k小值，插入删除都是O（logK），最壞情況下數組裡N個元素都會插入，是以需要O（NlogK）

    空間複雜度：O（K） 大頂堆裡最多有k個數