我有四个数组大小为2 ^ N，其中已经通过我的算法产生的阵列的N = 25元。这些排序，但包含的数字。现在，我必须采取ARRAY1的每个元素并选择ARRAY2，ARRAY3元素，array4他们这样一笔应该是最小的（当我说我总和可以采取A1 [K] + -A2 [J] + - A3 [M] + -A4 [T]。 我认为这是类似至K尺寸的合并问题。可有人点到文学/实施/启发式做同样的。 问候， Allahbaksh

I have four arrays of size 2^N where N = 25. The elements of arrays have been generated by my algorithm. These are sorted but contain numbers. Now I have to take each element of array1 and select elements of array2, array3, array4 such that sum of them should be minimum (when I say sum I can take a1[k] +-a2[j]+-a3[m]+-a4[t]. I think it is similar to K Dimension merge problem. Can some one point to the literature/implementation /heuristic for doing the same. Regards, Allahbaksh

推荐答案

我觉得这个问题可以在O（N）来解决，合并设置，以便第二个值将序列号在联盟所有阵列。遍历，并从4个值每一次迭代的形式回答，每一步计算最大距离选择的号码之间。 - >尽量减少这种价值 初始化结果阵列与每个阵列最小的数字。

I think this problem could be solved in O(n), merge all arrays in union set so second value will be array number. Iterate through it and on each iteration form answer from 4 values, on each step calculate maximum distance between selected numbers -> minimize this value. Init result array with smallest numbers from each array.

public Integer[] findClosest(int[][] unionSet, Integer[] result) {

    for (int i = 0; i < unionSet.length; i++) {
        int value = unionSet[i][0];
        int position = unionSet[i][1];
        int currentDistance = getDistance(result);
        Integer[] temp = Arrays.copyOf(result, result.length);
        temp[position] = value;
        int newDistance = getDistance(temp);
        if (newDistance <= currentDistance) {
            result = temp;
        }
    }
    return result;
}

private int getDistance(Integer[] result) {
    int max = 0;
    int min = 0;
    for (int i = 1; i < result.length; i++) {
        if (result[i] != null) {
            if (result[i] > result[max]) {
                max = i;
            }
            if (result[min] != null && result[i] < result[min]) {
                min = i;
            }
        }
    }

    return Math.abs(result[max] - result[min]);
}