算法-排序重構的問題，求解答

排序重構的問題，求解答

令A為一個由N個已特殊排序數組成的數列：A1，A2，…，AN，其中A1=0。令B為N（N-1）/2個數（定義為Dij=Ai-Aj(i>j)）組成的數列。例如，A=0，1，5，8，那麼D=1，3，4，5，7，8。請完成：
a） 編寫程序，根據A構造D；
b） 編寫程序，構造與D相對應的某一個數列A，注意A不是唯一的

最佳回答：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ArrayDemo {

    public static void main(String[] args) {
        Integer[] aArray = new Integer[] { 0, 1, 5, 8 };

        // 第一步獲取D數組
        System.out.println("根據A計算得到的數組D:");
        Integer[] dArray = getDArray(aArray);

        for (int i = 0; i < dArray.length; i++) {
            System.out.println(dArray[i]);
        }
        // 第二步根據D數組反求A數組
        System.out.println("反求得到的數組A:");
        Integer[] _aArray = getAArray(dArray);
        for (int i = 0; i < _aArray.length; i++) {
            System.out.println(_aArray[i]);
        }
    }

    /**
     * 構造與D相對應的某一個數列A，注意A不是唯一的
     * 
     * @param dArray
     * @return
     */
    private static Integer[] getAArray(Integer[] dArray) {
        int dLen = dArray.length;
        int aLen = getALen(dLen);
        if (aLen == 0) {
            System.err.println("計算A的數組出錯，請確認傳入的D數組有效。");
            return null;
        }

        // 因為A1必須為0，可以直接確定A1，並設置A最後一個值為D的最後一個值，保證了最大值。同時A2=A1+D1,A3=A2+D2,依次類推，認為D是有序數組，遍歷D數組得到中間A的所有數據
        Integer[] aArray = new Integer[aLen];
        aArray[0] = 0;
        aArray[aLen - 1] = dArray[dLen - 1];
        for (int i = 1; i < aLen - 1; i++) {
            aArray[i] = aArray[i - 1] + dArray[i];
        }
        return aArray;
    }

    /**
     * 根據傳入的D數組的長度求出A數組的長度來，就是解一元二次方程n*n-n=2*dLen,n代表A數組的長度
     * 
     * @param dLen
     * @return
     */
    private static int getALen(int dLen) {
        for (int n = 2; n <= 2 * dLen; n++) {
            if (n * n - n - 2 * dLen == 0) {
                return n;
            }
        }
        return 0;
    }

    /**
     * 令aArray為一個由N個已特殊排序數組成的數列：A1，A2，…，AN，其中A1=0。令D為N（N-1）/2個數（定義為Dij=Ai-Aj(i>j
     * )組成的數列。例如，A=0，1，5，8，那麼D=1，3，4，5，7，8
     * 
     * @param aArray
     * @return
     */
    private static Integer[] getDArray(Integer[] aArray) {
        int aLen = aArray.length;
        int dLen = aLen * (aLen - 1) / 2;
        List<Integer> tempList = new ArrayList<Integer>();
        for (int i = 0; i < aArray.length; i++) {
            for (int j = i + 1; j < aArray.length; j++) {
                if (tempList.size() == dLen) {
                    i = aLen;
                    break;
                } else {
                    tempList.add(aArray[j] - aArray[i]);
                }
            }
        }
        Integer[] dArray = tempList.toArray(new Integer[0]);
        Arrays.sort(dArray);
        return dArray;
    }
}