Java找N個數中最小的K個數，PriorityQueue和Arrays.sort()兩種實作方法

最近看到了

java.util.PriorityQueue

。剛看到還沒什麼感覺，今天突然發現他可以用來找N個數中最小的K個數。

假設有如下 10 個整數。

怎麼找出最小的 5 個數呢？很好想到的方法是先升序排序，然後取前 5 個就可以。

至于怎麼排序方法有很多，比如簡單的冒泡，選擇，”難點”的有快速，希爾和堆等等。

先看看這種比較少見的實作方法的代碼，再看看下面的簡單介紹。

PriorityQueue實作

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class FindSmallestKofNNumbers {

	public List<Integer> findSmallestKofNNumbers(	int[] numbers,
													int k) {

		Queue<Integer> queue = new PriorityQueue<>();
		for (int i : numbers) {
			queue.add(i);
		}

		List<Integer> ans = new ArrayList<>();
		for (int i = 0; i < k; ++i) {
			ans.add(queue.poll());// 取k個數加到清單中
		}

		return ans;
	}

}
           

看完沒，代碼簡單吧，核心代碼就幾句。建立一個

PriorityQueue

對象，調用

add

方法和

poll

方法。

1. 建立一個

   Integer

   類型的一個基于優先級堆的無界優先級隊列。元素是按照隊列元素的自然順序進行排序。此隊列的頭是按指定方式确定的最小的元素，如果多個元素都是最小值，則頭是其中一個元素——選擇方法任意。

2. boolean add(E e)

   将 e 插入此優先級隊列。

3. E poll()

   擷取并移除此隊列的頭，如果此隊列為空，則傳回

   null

   。

Arrays.sort()實作

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FindSmallestKofNNumbers {

	public List<Integer> findSmallestKofNNumbers(	int[] numbers,
													int k) {

		int[] arr = Arrays.copyOf(numbers, numbers.length);
		Arrays.sort(arr);

		List<Integer> ans = new ArrayList<>();
		for (int i = 0; i < k; ++i) {
			ans.add(arr[i]);// 取k個數加到清單中
		}

		return ans;
	}

}
           

參考

[1] Class PriorityQueue<E>[OL].oracle，2019.

[2] 王一飛. PriorityQueue詳解[OL].簡書，2018.