找到N个最接近的数字

Question

有一个二维数组,如 -

a[0] = [ 0 , 4 , 9 ]
a[1] = [ 2 , 6 , 11 ]
a[2] = [ 3 , 8 , 13 ]
a[3] = [ 7 , 12 ]

需要从每个子阵列中选择一个元素,使得结果数组最接近,即集合中最高数字和最低数字之间的差异最小.

上面的答案是= [ 9 , 6 , 8 , 7 ].

做了算法,但感觉不是很好.在时间和空间复杂性方面,这样做的有效算法是什么？

编辑 - 我的算法(在python中) -

INPUT - Dictionary : table{}
OUTPUT - Dictionary : low_table{}
#
N = len(table)
for word_key in table:
    for init in table[word_key]:
        temp_table = copy.copy(table)
        del temp_table[word_key]
        per_init = copy.copy(init)
        low_table[init]=[]
        for ite in range(N-1):
            min_val = 9999
            for i in temp_table:
                for nums in temp_table[i]:
                    if min_val > abs(init-nums):
                        min_val = abs(init-nums)
                        del_num = i
                        next_num = nums
            low_table[per_init].append(next_num)
            init = (init+next_num)/2
            del temp_table[del_num]
lowest_val = 99
lowest_set = []
for x in low_table:
    low_table[x].append(x)
    low_table[x].sort()
    mini = low_table[x][-1]-low_table[x][0]
    if mini < lowest_val:
        lowest_val = mini
        lowest_set = low_table[x]
print lowest_set

Answer 1

收集所有值以创建单个有序序列,每个元素用它来自的数组标记:0(0),2(1),3(2),4(0),6(1),... 12(3),13(2)

然后在它们之间创建一个窗口,从第一个开始(0(0))并在第一个位置结束,使窗口跨越所有数组(0(0) - > 7(3))

然后通过将窗口的开头递增1来滚动此窗口,并递增窗口的末尾,直到再次有一个覆盖所有元素的窗口.

然后再次滚动:(2(1),3(2),4(0),...... 7(3)),依此类推.

在每个步骤中跟踪最大和最小之间的差异.最终你会发现窗口最小的那个.我觉得在最坏的情况下这是O(n ^ 2),但这只是猜测.