14

次のような2次元配列を持っています-

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

結果の数値セットが最も近くなるように、各サブ配列から 1 つの要素を選択する必要があります。つまり、セット内の最大数と最小数の差が最小になります。

上記の答えは = になります[ 9 , 6 , 8 , 7 ]。

アルゴリズムを作成しましたが、良いものだとは感じません。時間と空間の複雑さの観点から、これを行うための効率的なアルゴリズムは何でしょうか?

編集 - 私のアルゴリズム(python) - 

入力 - 辞書: テーブル{}
OUTPUT - 辞書: low_table{}
#
N = len(テーブル)
テーブルの word_key の場合:
    テーブルの初期化[word_key]:
        temp_table = copy.copy(テーブル)
        del temp_table[単語キー]
        per_init = copy.copy(init)
        low_table[初期化]=[]
        範囲内のアイテムの場合（N-1）：
            最小値 = 9999
            for i in temp_table:
                temp_table[i] の数値の場合:
                    min_val > abs(init-nums) の場合:
                        min_val = abs(init-nums)
                        del_num = i
                        next_num = 数値
            low_table[per_init].append(next_num)
            init = (init+next_num)/2
            デル一時テーブル[デル番号]
最低値 = 99
最低セット = []
low_table の 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)) にまたがる最初の位置で終了する、それらにまたがるウィンドウを作成します。

次に、ウィンドウの開始を 1 ずつインクリメントしてこのウィンドウをロールし、すべての要素をカバーするウィンドウが再び得られるまで、ウィンドウの終了をインクリメントします。

次に、もう一度ロールします: (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) であることに注意してください。これは、内側のループが各配列の値ごとに最大 1 回実行されるためです。

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 に答える