給定一個數組，找出每個元素的最後一個較小元素

給定一個數組爲每個元素找到數組中最後一個較小元素的索引。例如，假設給定的數組是{4,2,1,5,3}。然後，每個元素的最後一個更小的元素將如下所示。爲第一對4-> 3給定一個數組，找出每個元素的最後一個較小元素

4->3 
2->1 
1->Null 
5->3 
3->Null

通告，3是在陣列的最後一個元素小於4.

所得/輸出陣列將具有索引不元素本身。結果將是{4,2,-1,4,-1}

我在接受採訪時被問到這個問題，但我想不出一個解決方案比微不足道的O(n^2)解決方案更好。

任何幫助將不勝感激。

來源

2017-04-17 faizan

Make a list, add last element index. 
Walk through array right to left.  
For every element: 
    if list tail value is smaller then current element 
     find the most first smaller list element (binary search, list is sorted) 
    otherwise 
     add element index to the list tail, output -1

爲{4,2,1,5,3,6,2}例如列表將包含index 6 (value 2); index 2 (value 1)

來源

2017-04-17 08:31:33 MBo

以一個數組爲例：'{4,2,1,5,3,6,2}'。當我從正確的過程。添加3,6,2 - '3（root）2（Left）6（right）' 現在加入'3,6,2'後，對於元素5，我們將查看樹（插入5之前）。 2存在較小的值 - 3和2.要選擇的正確值是2，但是如果我使用底層函數，那麼它會給我3. 那麼我們如何選擇較小的值？ – faizan

似乎我理解條件'最後一個小元素'錯了。 – MBo

添加新方法。 – MBo

我們需要計算max(index)在數值越小的所有元素。

讓我們按照字典順序排列對（元素，索引）並對它們進行迭代，記錄到目前爲止所看到的最大索引。這正是最右邊小元素的位置。這裏有一個如何能實現它：

def get_right_smaller(xs): 
    res = [-1] * len(xs) 
    right_index = -1 
    for val, idx in sorted((val, idx) for idx, val in enumerate(xs)): 
     res[idx] = right_index if right_index > idx else -1 
     right_index = max(right_index, idx) 
    return res

此解決方案，甚至如果正確輸入數組包含相同的數字，因爲較小的指數元素前面去，如果兩個元素的值是相同的。

該解決方案的時間複雜度爲O(N log N + N) = O(N log N)（它確實排序和一次線性傳遞）。

如果數組中的所有元素都是O(N)，則可以使用計數排序使此解決方案成爲線性。

來源

2017-04-17 15:11:05 kraskevich

偉大的解決方案！ –

給定一個數組，找出每個元素的最後一個較小元素

回答

相關問題