Match Three or More Nearest Numbers from arrays

问题:

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

回答1:

Step 1 For array1[k], find a number in array2 or array3 or array4 such that its modulus is closer to 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

Step 2 Then of the remaining 2 arrays, find a pair of numbers which are closer to each other. (again consider modulus)

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

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

Eventually you get min(a1[k] +-a2[j]+-a3[m]+-a4[t]) from all 4 arrays.

回答2:

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