題目描述
給定一個陣列ar和一個支點p,p=ar[0],並將陣列ar依據支點p劃分為left(左邊)、right(右邊)或是equal(相等)。left為小於支點p的所有元素,right為大於支點p的所有元素,equal為等於支點p的所有元素(包含支點p)。
原題網址
輸入格式
輸入第一行為一個整數n,範圍在1到1000之間(包含1和1000)。
第二行為n個用空格分隔的整數,範圍在-1000到1000之間(包含-1000和1000),不會重複。
輸出格式
輸出只有一行,依序輸出劃分之後left、equal、right這三個集合中的元素,以空格分隔。
範例輸入
5
4 5 3 7 2
4 5 3 7 2
範例輸出
3 2 4 5 7
額外解釋
支點p是3。比3小的元素會被分到left集合,等於3的元素會被分到equal集合,比3大的元素會被分到right集合。
因此劃分之後,
left = [2]
equal = [3]
right = [4, 5, 7]
所以會輸出「2 3 4 5 7」。
解題概念
劃分(divide)是快速排序法的一個很重要的概念,可以將一個大問題拆解成小問題。有關於快速排序法的詳細介紹,可以參考這篇文章:
若要達成這個題目的需求,因為元素不會重複,可以知道equal集合只會有支點p本身,所以可以只另外建立出left和right集合來儲存比大小之後的結果。又由於支點p已經固定好是在索引0的位置,因此只要從索引1開始,把陣列索引1之後的元素都與支點p進行大小比對,把結果存入left和right集合中。最後再把left、支點p和right集合串接在一起輸出即可。
參考答案
import java.util.*;
public class Solution {
public static void main(final String[] args) {
final Scanner in = new Scanner(System.in);
final int n = in.nextInt();
final ArrayList<Integer> left = new ArrayList<>();
final ArrayList<Integer> right = new ArrayList<>();
final int p = in.nextInt();
for (int i = 1; i < n; i++) {
final int e = in.nextInt();
if (e <= p) {
left.add(e);
} else {
right.add(e);
}
}
left.add(p);
left.addAll(right);
final StringBuilder sb = new StringBuilder();
left.stream().forEach((e) -> {
sb.append(e).append(' ');
});
System.out.println(sb.toString().trim());
}
}