algorithm - 匹配数组中三个或更多最近的数字

Question

我有四个大小为 2^N 的数组，其中 N = 25。数组的元素是由我的算法生成的。这些已排序但包含数字。现在我必须取 array1 的每个元素并选择 array2、array3、array4 的元素，这样它们的总和应该是最小的（当我说 sum 我可以取 a1[k] +-a2[j]+-a3[m] +-a4[t]。我认为它类似于 K 维度合并问题。有人可以指出文献/实现/启发式做同样的事情。问候，Allahbaksh

Answer 1

我认为这个问题可以在 O(n) 中解决，合并联合集中的所有数组，所以第二个值将是数组编号。遍历它并在每次迭代中从 4 个值中得到答案，在每一步计算所选数字之间的最大距离 -> 最小化该值。
初始化每个数组中数字最小的结果数组。

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]);
}

Answer 2

步骤 1 对于array1[k]，在array2 或array3 或array4 中找到一个数，使其模数更接近于array1[k]。

eg . 
array1 = {1, 3, 67}
array2 = {-31, 7, 47}
array3 = {-1, 2, 10}
array4 = {14, 15, 66}

For array1[0] (ie. 1), the number closest to it is in array3 and its -1 as mod(-1) = 1

步骤 2 然后在剩下的 2 个数组中，找到一对彼此更接近的数字。（再次考虑模数）

eg . 
array2 = {-31, 7, 47}
array4 = {14, 15, 66}

Closest elements are 7 and 14 with -7 + 14 = 7.

最终你从所有 4 个数组中得到 min(a1[k] +-a2[j]+-a3[m]+-a4[t]) 。