配列が与えられた場合、各要素の最後の小さい要素を見つけよう。

Question

配列を渡すと、各要素の最後の小さな要素の配列の配列を見つける。

たとえば、指定された配列が{4,2,1,5,3}であるとします。次に、各要素の最後の小さな要素は次のようになります。 1対4-> 3

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

通知は、3より小さい4

得/出力アレイは要素自体のインデックスを持っていないであろう配列の最後の要素です。結果は{4,2,-1,4,-1}

私はこの質問にインタビューで尋ねられましたが、私は解決策が簡単なO(n^2)ソリューションよりも良いとは思えませんでした。

ご協力いただければ幸いです。

Answer 1

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}例のリストについては、我々は小さな値を持つすべての要素の上にmax(index)を計算する必要がindex 6 (value 2); index 2 (value 1)

Answer 2

含まれています。

ペア（要素、インデックス）を辞書順にソートし、今までに見た最大のインデックスを追跡しながら繰り返しましょう。それはちょうど右端の小さな要素の位置です。ここでは1がそれを実装できる方法は次のとおりです。

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 

このソリューションは、2つの要素の値が同じであれば小さいインデックスを持つ要素は、先に行くので、入力配列が同じ数字が含まれている場合でも正常に動作します。

このソリューションの時間的複雑度は、O(N log N + N) = O(N log N)（ソーティングと1回の直線パス）です。

配列のすべての要素がO(N)である場合、このソート方法をカウントソートを使用して線形にすることができます。