題目描述

給定一個陣列ar和一個支點p,p=ar[0],並將陣列ar依據支點p劃分為left(左邊)、right(右邊)或是equal(相等)。left為小於支點p的所有元素,right為大於支點p的所有元素,equal為等於支點p的所有元素(包含支點p)。



原題網址

https://www.hackerrank.com/challenges/quicksort1

輸入格式

輸入第一行為一個整數n,範圍在1到1000之間(包含1和1000)。

第二行為n個用空格分隔的整數,範圍在-1000到1000之間(包含-1000和1000),不會重複。

輸出格式

輸出只有一行,依序輸出劃分之後left、equal、right這三個集合中的元素,以空格分隔。

範例輸入

5
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)是快速排序法的一個很重要的概念,可以將一個大問題拆解成小問題。有關於快速排序法的詳細介紹,可以參考這篇文章:

https://magiclen.org/quick-sort/

若要達成這個題目的需求,因為元素不會重複,可以知道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());
    }
}