[HackerRank]最接近的數字(Closest Numbers)

題目描述

給定一個未排序的整數陣列，您可以找出一組差的絕對值最小的元素嗎？如果有好幾組元素差的絕對值都一樣小，那就把它們全都找出來吧！

原題網址

輸入格式

輸入第一行是一個整數N，範圍在2到2000000之間(包含2和200000)，代表陣列的元素數量。

第二行輸入陣列的所有元素，以空格隔開。元素值的範圍在10^-7到10⁷之間(包含10^-7和10⁷)，且不會重複。

輸出格式

輸出差的絕對值為最小的那組元素值。如果有很多組，就把它們遞增輸出。輸出都在同一行上，元素和元素值之間以空格分隔。如果有元素同時存在於答案的不同組，必須將它重複輸出(詳見範例3)。

範例輸入1

範例輸出1

額外解釋1

|-20 - 30| = 50，50為此陣列中「任一組元素相減的絕對值」的最小值。

範例輸入2

範例輸出2

額外解釋2

|-470 - (-520)| = |-20 - 30| = 50，50為此陣列中「任一組元素相減的絕對值」的最小值。

範例輸入3

範例輸出3

額外解釋3

此陣列中「任一組元素相減的絕對值」的最小值為1，|5 - 4| = |4 - 3| = |3 - 2| = 1。(2, 3)一組，(3, 4)一組，(4, 5)一組，因此元素「3」、「4」會被重複輸出。

解題概念

將輸入的陣列先用快速排序法排序做遞增排序。有關於快速排序法的說明可以參考這篇文章：

為什麼要先排序？因為排序後的元素只要去與其位置相鄰的元素進行相減取絕對值的運算即可，算出來的值雖然不一定是陣列中最小的元素差的絕對值，但它對於這個元素能與其它元素算出來的差的絕對值來說絕對會是最小的。

建立一個ArrayList陣列，用來儲存擁有最小元素差的絕對值的一組元素在已排序陣列中出現的索引位置。

使用一個變數來記錄目前遇到的差的絕對值的最小值，並從頭開始走訪已排序陣列，計算相鄰元素的差的絕對值。如果計算出來的差的絕對值比已知的絕對值的最小值還要小，則清空ArrayList陣列，並記錄目前走訪的索引位置；如果計算出來的差的絕對值剛好等於已知的絕對值的最小值，將目前走訪的索引位置存到ArrayList陣列中。

最後再使用StringBuilder，利用ArrayList陣列中儲存的索引資訊，依序輸出元素值即可。

參考答案

import java.util.*;

public class Solution {

    public static void quickSortIterative(final int[] array) {
        final int[] stack = new int[array.length];
        int top = -1;
        int s, e;
        stack[++top] = 0;
        stack[++top] = array.length - 1;
        while (top >= 0) {
            e = stack[top--];
            s = stack[top--];
            final int x = array[s]; // pivot
            int l = s + 1;
            int r = e;
            while (true) {
                while (r > s && array[r] >= x) {
                    --r;
                }
                while (l <= r && array[l] <= x) {
                    ++l;
                }
                if (l < r) {
                    final int buffer = array[l];
                    array[l] = array[r];
                    array[r] = buffer;
                } else {
                    if (r > s) {
                        final int buffer = array[r];
                        array[r] = array[s];
                        array[s] = buffer;
                    }
                    break;
                }
            }
            final int ls = s, le = r - 1;
            final int rs = r + 1, re = e;
            final int ll = le - ls + 1, rl = re - rs + 1;
            if (ll > 1) {
                stack[++top] = ls;
                stack[++top] = le;
            }
            if (rl > 1) {
                stack[++top] = rs;
                stack[++top] = re;
            }
        }
    }

    public static void main(final String[] args) {
        final Scanner in = new Scanner(System.in);
        final int n = in.nextInt();

        final int[] A = new int[n];

        for (int i = 0; i < n; ++i) {
            A[i] = in.nextInt();
        }
        quickSortIterative(A);

        final ArrayList<Integer> smallestPair = new ArrayList<>();
        final int n_dec = n - 1;
        int smallDifference = Integer.MAX_VALUE;
        for (int i = 0; i < n_dec; ++i) {
            final int d = A[i + 1] - A[i];
            if (d <= smallDifference) {
                if (d < smallDifference) {
                    smallDifference = d;
                    smallestPair.clear();
                }
                smallestPair.add(i);
            }
        }
        final StringBuilder sb = new StringBuilder();
        for (final int index : smallestPair) {
            sb.append(A[index]).append(" ").append(A[index + 1]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}