14

有一个二维数组，比如 -

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

需要从每个子数组中选择一个元素，以使结果集的数字最接近，即集合中最大数字和最小数字之间的差最小。

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

做了一个算法，但感觉不是很好。就时间和空间复杂度而言，什么是有效的算法？

编辑 - 我的算法（在 python 中） - 

输入 - 字典：表{}
输出 - 字典：low_table{}
#
N = len(表)
对于表中的 word_key：
    对于表中的初始化[word_key]：
        temp_table = copy.copy（表）
        del temp_table[word_key]
        per_init = copy.copy(init)
        低表[初始化]=[]
        对于范围内的项目（N-1）：
            min_val = 9999
            对于 temp_table 中的 i：
                对于 temp_table[i] 中的 nums：
                    如果 min_val > abs(init-nums):
                        min_val = abs(init-nums)
                        del_num = 我
                        next_num = 数字
            low_table[per_init].append(next_num)
            初始化 = (init+next_num)/2
            del temp_table[del_num]
最低值 = 99
最低集 = []
对于低表中的 x：
    low_table[x].append(x)
    low_table[x].sort()
    迷你 = low_table[x][-1]-low_table[x][0]
    如果迷你 < 最低值：
        最低值 = 迷你
        最低集 = 低表 [x]
打印最低集

4

3 回答 3

11

收集所有值以创建单个有序序列，每个元素都用它来自的数组标记：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) 但这只是一个猜测。

于 2013-07-16T02:37:37.590 回答
2

whiterook6 的漂亮算法的冗长 Haskell 版本：

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)]
于 2013-07-17T02:57:58.147 回答
1

我有一个 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)
于 2013-07-21T06:28:06.060 回答