在基於多個字段

用戶定義的對象的陣列查找LIS開裂編碼面試（第5版）：CHP 11，QUES 7在基於多個字段

問題：馬戲團正在設計的塔架例程包括人站在彼此的肩膀上。出於實際和美學的原因，每個人都必須比他或她下面的人短而輕。考慮到馬戲團中每個人的身高和體重，請編寫一種方法來計算這樣一座塔樓中人數最多的人。

我的疑問：

在它在文本明確提到，排序的元素將會使溶液太微不足道，那麼爲什麼元素已經在代碼最初排序的書給出的解決方案？

如果元素並不需要留在同一個（相對）的命令，那麼我們將在陣列只會排序。這使問題變得微不足道，因此讓我們假設元素需要保持相同的相對秩序。

這裏是從書其中排序已經完成（前三行的代碼）的代碼：

ArrayList<HtWt> getIncreasingSequence(ArrayList<HtWt> items)  
    {  
     Collections.sort(items);  
     return longestIncreaingSequence(items);  
    }

來源

2017-06-05 Gaurang Singhal

請給出一個比源代碼縮寫更具描述性的標題，每個問題限制自己一個問題。通過使用引用塊來清楚引用哪些部分，並聲明源（不是縮寫，而不是標題）。 –

@MarkRotteveel完成 –

@MarkRotteveel請按照我提出的更改，刪除downvote。 –

提出的解決方案是由2個步驟：

排序按重量計
找到高度最長的子序列

引用的句子與第一步不是相關的，而是第二步（找到最長的遞增子序列），它解釋了我們不能僅僅排序高度，因爲我們不能改變它們的順序，因爲它們已經是按其權重排序。

看看這個例子中，5人：

weights: 4 5 1 7 2 
heights: 6 3 5 4 1

結果在步驟1（重量比排序）：

weights: 1 2 4 5 7 
heights: 5 1 6 3 4

現在，看着我們可以看到的最長的高度增加的子序列是1 3 4，它告訴我們解決方案由3人組成。爲了獲得這個結果，我們不能僅僅根據高度進行排序，因爲它們已經按照它們的重量排序了......

...元素需要保持相同的相對順序。

因此，我們需要使用最長的遞增子序列算法。

來源

2017-06-09 22:23:38

我不認爲它意味着排序任何值，因爲它會改變順序的順序。否則，在對任何一個屬性進行排序之後，它就會成爲LIS問題，如前所述，這些屬性過於微不足道。 –

@GaurangSinghal引用的句子在關於LIS子問題的部分內，關於第2步。在本節中，有一個數組LIS的示例;引用的句子就是關於這個例子。然後解釋說，在主要問題中應該使用與步驟2相同的方法，其中在按重量分類後，我們不能改變高度的順序。是的，這個問題是關於LIS排序後的問題之一。 –

在再次閱讀問題陳述和解決方案之後，看起來你是對的。儘管我解決了這個問題，但考慮到我們無法改變元素的順序（甚至不是基於一個屬性），使它變得更具挑戰性。謝謝。 –

在基於多個字段

回答

相關問題