[HackerRank]快速排序1─劃分(Quicksort 1 - Partition)

題目描述

給定一個陣列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這三個集合中的元素，以空格分隔。

範例輸入

範例輸出

額外解釋

支點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());
    }
}