我們給出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,因爲我們永遠不能對它進行排序。
你可以用一些例子解釋一下嗎?我無法獲得python,或者C++/java中的代碼會很好 – Mrinal 2015-04-04 07:27:19
您是否使用基於1的索引? – Mrinal 2015-04-04 07:32:55
@Mrinal Python非常簡單,幾乎就像僞代碼。嘗試把它看作僞代碼,你會看到你理解它。請注意:'range(x)'產生所有值[0,1,...,x-1]','X'中的i表示每個循環,'len(X)'是數組的長度X(java的'X.length') – amit 2015-04-04 07:35:25