應用轉換使數組排序

Question

我們給出M個數字，每個數字都有一個與它關聯的值列表。我們可以用列表中的任何數字來改變它（它也只會在1到M之間）。

所以我們有（最大尺寸可以達到200×200）：

vector<vector<int>> transformations 

現在，我們正與N個整數另一個數組，我們要使它在增加順序排序。

注意：我們只能更改一次數字。

我們需要告訴要更改的最小數字，以使其排序。如果不可能，那麼我們也必須返回-1作爲答案，否則將更改最小字母數。

此數組中的每個數字只能更改一次。所以我認爲必須有一些動態編程能夠幫助解決這個問題。 N可以達到20萬。我想到了貪婪的解決方案，但是這對某些情況不起作用。

喜歡說，我們有M = 3和如下矢量變換的矢量：

1->{1,2} 
2->{1,2} 
3->{3,4} 
4->{3,4} 

現在，如果N = 4和陣列[2,1,3,4]，然後回答是2，我們可以如果變換相同，N = 4，數組爲[3,4,1,2]，那麼答案爲-1，因爲我們永遠不能對它進行排序。

Answer 1

它可以使用動態編程遵循下遞歸公式來解決：

• i是索引
• x是從一組可填充每個指數的值（可以轉化爲基於索引的容易這些值）

D(0)(x) = 1 | x is not the original value //1 value array is sorted 
D(0)(x) = 0 | x is the original value 
D(i)(x) = min{D(i-1)(y) +1 | y < x} U { D(i-1)(y) | y<x, y is original value} U {INFINITY} 

的

的想法是採取最小的可能值之間的i,x每個值：

• D(i-1)(y) +1 | y < x} - 任何掉
• { D(i-1)(y) | y<x, y is original value} - 沒有交換需要
• {INFINITY} - 沒有辦法得到一個排序的數組這個位置

Python代碼：

orig = [2,1,3,4] 
vals = [[1,2],[1,2],[3,4],[3,4]] 
D = [[1,1]] 
for x in range(len(vals[0])): 
    if vals[0][x] == orig[0]: 
     D[0][x] = 0 
    else: 
     vals[0][x] = 1 
for i in range(1,len(orig)): 
    D.append([max_int32, max_int32]) 
print D 
for i in range(1,len(orig)): 
    for x in range(len(vals[i])): 
     for y in range(len(vals[i-1])): 
      if vals[i-1][y] < vals[i][x] and vals[i][x] != orig[i]: 

       D[i][x] = min(D[i][x],D[i-1][y] + 1) 
      elif vals[i-1][y] < vals[i][x]: 
       D[i][x] = min(D[i][x],D[i-1][y]) 
print min(D[len(orig)-1]) 

對於其他陣列，需要修改orig和vals因此，例如用於[3,4,1,2]：

orig = [3,4,1,2] 
vals = [[3,4],[3,4],[1,2],[1,2]] 

這裏，max_int32表明它不能做 - 你可以輕鬆地將其交換到-1。