An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

題目說，有一組數組original
依照步驟
1.將original中的每個數字的兩倍附加到自身後面
2.整組打亂後獲得新數組changed
我們的目標就是把changed通過上述規則還原成original，無法還原就返回空數組

我的解題思路：
先思考changed應該要有的幾項特點

• 數組長度一定是偶數
• 每個元素都會配對成 x和2x 的組合

所以具體的解題方法應該是：
1.檢查數組長度，若為奇數直接返回空數組
2.把出現的數字做成一個陣列
3.針對每個數字n，做乘2的動作得到2n
4.如過2n存在陣列裡面，同時刪除這兩個數字並把n存到original
5.如過2n不存在陣列裡，則把n除以2得到n/2，
6.如過n/2存在陣列裡面，同時刪除這兩個數字並把n/2存到original
7.如過n/2依然不存在陣列裡，則返回空數組
8.成功遍歷完所有陣列的數後，返回original

class Solution {
    public int[] findOriginalArray(int[] changed) {
        // 檢查數組長度
        if (changed.length % 2 != 0) {
            return new int[0];
        }
        // 把數字放進陣列
        List<Integer> numsList = new ArrayList<>();
        for (int num : changed) {
            numsList.add(num);
        }
        List<Integer> original = new ArrayList<>();
        // 開始遍歷配對
        while (!numsList.isEmpty()) {
            int n = numsList.remove(0);
            // 2*n
            Integer doublee = n* 2;
            if (numsList.contains(doublee)) {
                numsList.remove(doublee);
                original.add(n);
            } else {
                // 找不到就嘗試n/2
                if (n % 2 == 0) {
                    Integer half = n / 2;
                    if (numsList.contains(half)) {
                        numsList.remove(half);
                        original.add(half);
                    } else {
                        // 還是找不到
                        return new int[0];
                    }
                } else {
                    // n是奇數
                    return new int[0];
                }
            }
        }
        int[] result = new int[original.size()];
        for (int i = 0; i < original.size(); i++) {
            result[i] = original.get(i);
        }
        return result;
    }

我最近開始感覺到一點刷題的樂趣了！
可能是因為難度適中，挫折感和成就感取得了平衡吧？
總之經果一些小地方修改後，今天也挑戰成功～～