8

これは私が見つけた興味深いパズルです。これによれば、配列が与えられた場合、その中の忍者インデックスを見つける必要があります。

Ninja インデックスは、次のルールによって定義されます。

より小さいインデックスを持つすべての要素が A[K] 以下の値を持ち、より大きいインデックスを持つすべての要素が A[K] 以上の値を持つようなインデックス K。

たとえば、次のことを考慮してください。

A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9.

この場合、5r = [0,k] および A[5]<=A[r] r = [k,n] に対して A[r]<=A[5] であるため、 は ninja index です。

O(n) でそれを見つけるために、どのアルゴリズムに従う必要がありますか。私はすでにブルートフォース O(n^2) ソリューションを持っています。

EDIT : 複数の ninja index が存在する可能性がありますが、できれば最初のものを見つける必要があります。NI がない場合は、-1 を返します。

4

4 に答える 4

8

配列のすべてのサフィックスの最小値とすべてのプレフィックスの最大値を事前に計算します。このデータを使用すると、O(1) で Ninja のすべての要素をチェックできます。

于 2012-09-20T15:06:28.103 に答える
2

O(3n) 操作を行う Python ソリューション

def n_index1(a):
    max_i = []
    maxx = a[0]
    for j in range(len(a)):
        i=a[j]

        if maxx<=i and j!=0:
            maxx=i
            max_i.append(1)

        else:
            max_i.append(-1)



    return max_i

def n_index2(a):
    max_i = []
    maxx = -a[len(a)-1]
    for j in range(len(a)-1,-1,-1):
        i=-a[j] # mind the minus

        if maxx<=i and j!=len(a)-1:         
            maxx=i
            max_i.append(1)

        else:
            max_i.append(-1)

    return max_i

def parse_both(a,b):
    for i in range(len(a)):
        if a[i]==1 and b[len(b)-1-i]==1:
            return i

    return -1


def ninja_index(v):
    a = n_index1(v)
    b = n_index2(v)

    return parse_both(a,b)
于 2012-09-20T16:34:14.067 に答える
2

同じ一般的なアプローチに従う別の Python ソリューション。もう少し短いかもしれません。

def ninja(lst):
    maxs = lst[::]
    mins = lst[::]
    for i in range(1, len(lst)):
        maxs[   i] = max(maxs[   i], maxs[ i-1])
        mins[-1-i] = min(mins[-1-i], mins[-i  ])
    return [i for i in range(len(lst)) if maxs[i] <= lst[i] <= mins[i]]

リストコピーアクションに関しては少し最適化できると思いますが、この方法ではより簡潔になります。

于 2012-09-20T17:42:12.113 に答える
0

この単純な Java コードは、プロパティ「右方向のすべての要素が少なくない」を持つ左端のインデックスを計算します。

private static int fwd(int[] a) {
    int i = -1;
    for (int j = 0; j < a.length - 1; j++) {
        if (a[j + 1] >= a[j] && i == -1) {
            i = j + 1;
        } else if (i != -1 && a[j + 1] < a[i]) {
            i = -1;
        }
    }
    return i;
}

ほぼ同じコードで、「左方向のすべての要素は大きくない」というプロパティを持つ左端のインデックスを計算します。

private static int bwd(int[] a) {
    int i = -1;
    for (int j = 0; j < a.length - 1; j++) {
        if (a[j + 1] >= a[j] && i == -1) {
            i = j + 1;
        } else if (i != -1 && a[j + 1] < a[i]) {
            i = -1;
        }
    }
    return i;
}

結果が同じ場合は、一番左の Ninja インデックスが見つかります。

于 2012-09-25T20:32:24.260 に答える