寻找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编写)-

输入 - 字典：table{}
输出 - 字典：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

- Anirudh

---

请展示你的算法。 - Dhaivat Pandya

这让我想起了背包问题，可能是NP完全问题。 - Codie CodeMonkey

不确定这是否是背包问题。能详细解释一下吗？ - Dhaivat Pandya

这不是背包问题，但看起来很相似。背包问题要求选择适合放入背包的物品，使得价值最大化。而这个问题要求从每个袋子中选择一个物品放入你的背包中，使得某些东西最小化。它类似于分割背包问题。 - Codie CodeMonkey

行是否保证已排序？这很重要。 - roippi

Answer 1

收集所有值以创建一个单一有序序列，每个元素都带有它来自的数组的标记：0（0），2（1），3（2），4（0），6（1），... 12（3），13（2）

然后在它们之间创建一个窗口，从第一个开始（0（0）），并将其结束于使窗口跨越所有数组的第一个位置（0（0）-> 7（3））

然后通过递增窗口的开始并递增窗口的结束，直到再次拥有覆盖所有元素的窗口，来滚动此窗口。

然后再次滚动它：（2（1），3（2），4（0），... 7（3）），依此类推。

在每个步骤中，跟踪最大值和最小值之间的差异。最终找到具有最小窗口的一个。我感觉在最坏情况下这是O（n ^ 2），但这只是猜测。

- whiterook6

---

排序的时间复杂度是 O(n.log(n))，然后滑动窗口的时间复杂度就只有 O(n) 了。这是因为指针从不减少。最多只能有 2.n 个可能的窗口。 - necromancer

如果原始列表已排序（如所示示例），则将列表合并为一个排序列表的时间是线性的。 - Dave

你可能想要从数组ID（数字来自哪个不同的数组）中保留哈希到窗口中的计数。然后，您就知道何时移动前索引和何时移动后索引。 - Dave

是的，它运行正常。在移动窗口的后索引时，需要添加一些更多的功能。 - Anirudh

@DaveGalvin 很酷，更好的是——O(n)一路顺畅！请给我们相对较新的whiterook6点赞 =) - necromancer

Answer 2

一个啰嗦的Haskell版本，基于whiterook6的好算法：

import Data.List (minimumBy,sortBy)
import qualified Data.Map as M (fromList,toList,adjust,lookup)

f arrays = g (zip arrays [1..]) [] h [(100,0),(0,0)] where
  n = length arrays
  h = (M.fromList $ zip [1..n] (repeat 0))
  g arrays sequence indexes best
    | any ((==0) . snd) (M.toList indexes) = 
        g (foldr comb [] arrays) (next:sequence) (M.adjust (+1) ind indexes) best
    | otherwise = 
        if null (drop 1 arrays) 
           then best'
           else g (foldr comb [] arrays) 
                  (next:init trimmedSequence) 
                  (foldr (M.adjust (+1)) h (ind : (map snd $ init trimmedSequence))) 
                  best'
   where 
     best' = minimumBy comp [best,trimmedSequence]
     next@(val,ind) = minimum $ map (\(arr,i) -> (head arr,i)) arrays
     comb a@(seq,i) b = if i == ind 
                           then if null (drop 1 seq) 
                                   then b 
                                   else (drop 1 seq,i) : b 
                           else a : b
     comp a b = compare (fst (head a) - fst (last a)) (fst (head b) - fst (last b))
     trimSequence []     _ = []
     trimSequence (x:xs) h
       | any ((==0) . snd) (M.toList h) = 
           case M.lookup (snd x) h of
             Just 0     -> x : trimSequence xs (M.adjust (+1) (snd x) h)
             otherwise  -> trimSequence xs h
       | otherwise                      = []
     trimmedSequence = trimSequence sequence (M.fromList $ zip [1..n] (repeat 0))

输出：

*Main> f [[0,4,9],[2,6,11],[3,8,13],[7,12]]
[(9,1),(8,3),(7,4),(6,2)]

- גלעד ברקן

Answer 3

我有一个 whiterook 算法的变种，认为它更简单（除了初始排序步骤外，更清晰地是 O(N)）。

按顺序遍历 minval 中的所有值。在此过程中，我们保留大于等于 minval 的每个数组中最小值的索引。我们还保留这些索引中其相应数组元素的最大值。

当我们考虑完特定的 minval 时，我们可以增加包含 minval 的所有数组的索引，并在必要时更新 maxval。

以下是实现。请注意（除了初始排序），它是 O(N)，因为内部循环最多只执行一次每个数组中的每个值。

def minspan(aa):
    allnums = sorted(set(sum(aa, [])))
    ntoi = dict((x, []) for x in allnums)
    for i in xrange(len(aa)):
        for x in aa[i]:
            ntoi[x].append(i)
    indexes = [0] * len(aa)
    maxval = max(a[0] for a in aa)
    best = None
    for minval in allnums:
        if best is None or best[0] > maxval - minval:
            best = maxval - minval, minval, maxval
        for i in ntoi[minval]:
            indexes[i] += 1
            if indexes[i] >= len(aa[i]):
                return [min(x for x in a if x >= best[1]) for a in aa]
            maxval = max(maxval, aa[i][indexes[i]])

aa = [[0,4,9], [2,6,11], [3,8,13], [7,12]]
print minspan(aa)

- Paul Hankin