3

最適化する必要がある次の問題があります。特定の配列 (重複キーが許可されている場合) について、配列内の各位置について、 の右側にあるすべての大きな値と の左側にあるすべての小さな値iを計算する必要があります。私たちが持っている場合：ii

1 1 4 3 5 6 7およびi = 3(値 3) の左側の小さい値の数iは1(キーの繰り返しなし) であり、右側の大きい値の数は です3。

この問題のブルート フォース ソリューションは~N^2であり、余分なスペースがあれば、大きな値から小さな値を計算することができるため、複雑さが に軽減され~(N^2)/2ます。私の質問は次のとおりです。それを行うためのより速い方法はありますか? たぶんNlgN？計算を高速化できるデータ構造があると思います。

編集：返信と議論に感謝します。以下の 2 つの問題に対する 2 つの適切な解決策を見つけることができます。stackoverflow で開発者から学ぶことは常に楽しいことです。

4

4 に答える 4

3

これがO(n log n)解決策です。

@SayonjiNakate で示唆されているように、セグメント ツリー (実装では Fenwick ツリーを使用) を使用したソリューションはO(n log M)時間内に実行されます。ここMで、 は配列内で可能な最大値です。

まず、「左側の小さい要素の数」の問題は、配列を反転して否定することにより、「右側の大きい要素の数」の問題と等価であることに注意してください。したがって、以下の説明では、「左側の小さい要素の数」のみを説明します。これを「lesser_left_count」と呼びます。

lesser_left_count のアルゴリズム:

アイデアは、特定の数よりも小さい数の合計を見つけることができるようにすることです。

  1. treeサイズが uptoの配列を定義します。これは、表示された数値などMAX_VALUEの値を格納します。10

  2. 次に、配列をトラバースし、数値が表示されたら、その値を(更新操作num)に代入します。次に、数値の lesser_left_count は、現在の位置の左側にあるすべての小さい数値が に設定されているため、これまでの から (合計演算)までの合計です。1tree[num]num1num-11

シンプルですよね？フェンウィック ツリーを使用すると、更新と合計の操作をそれぞれO(log M)時間内に実行できます。ここMで、 は配列内で可能な最大値です。配列を繰り返し処理しているため、合計時間はO(n log M)です。

単純なソリューションの唯一の欠点は、M大きくなるにつれて大量のメモリを使用することです (コードで設定M=2^20-1すると、約 4MB のメモリが必要になります)。これは、配列内の個別の整数をより小さな整数に (順序を維持する方法で) マッピングすることで改善できます。O(n log n)マッピングは、配列をソートするだけで実行できます。したがって、数値は「配列内の個別の要素の数」Mとして再解釈できます。

したがって、メモリはもう問題になりません。なぜなら、この改善の後、実際に巨大なメモリが必要な場合、それは配列に非常に多くの異なる数値がありO(n)、通常のマシンで計算するには時間の複雑さがすでに高すぎることを意味するからです。とりあえず。

簡単にするために、コードにはその改善を含めませんでした。

ああ、フェンウィック ツリーは正の数に対してのみ機能するため、配列内の数値を最小の 1 に変換しました。これは結果を変更しないことに注意してください。

Python コード:

MAX_VALUE = 2**20-1
f_arr = [0]*MAX_VALUE

def reset():
    global f_arr, MAX_VALUE
    f_arr[:] = [0]*MAX_VALUE

def update(idx,val):
    global f_arr
    while idx<MAX_VALUE:
        f_arr[idx]+=val
        idx += (idx & -idx)

def cnt_sum(idx):
    global f_arr
    result = 0
    while idx > 0:
        result += f_arr[idx]
        idx -= (idx & -idx)
    return result

def count_left_less(arr):
    reset()
    result = [0]*len(arr)
    for idx,num in enumerate(arr):
        cnt_prev = cnt_sum(num-1)
        if cnt_sum(num) == cnt_prev: # If we haven't seen num before
            update(num,1)
        result[idx] = cnt_prev
    return result

def count_left_right(arr):
    arr = [x for x in arr]
    min_num = min(arr)
    if min_num<=0:                       # Got nonpositive numbers!
        arr = [min_num+1+x for x in arr] # Convert to minimum 1
    left = count_left_less(arr)
    arr.reverse()                        # Reverse for greater_right_count
    max_num = max(arr)
    arr = [max_num+1-x for x in arr]     # Negate the entries, keep minimum 1
    right = count_left_less(arr)
    right.reverse()                      # Reverse the result, to align with original array
    return (left, right)

def main():
    arr = [1,1,3,2,4,5,6]
    (left, right) = count_left_right(arr)
    print 'Array: ' + str(arr)
    print 'Lesser left count: ' + str(left)
    print 'Greater right cnt: ' + str(right)

if __name__=='__main__':
    main()

生成されます:

元の配列: [1, 1, 3, 2, 4, 5, 6]
少ない方の左の数: [0, 0, 1, 1, 3, 4, 5]
大きい右 cnt: [5, 5, 3, 3, 2, 1, 0]

またはJavaコードが必要な場合：

import java.util.Arrays;

class Main{
    static int MAX_VALUE = 1048575;
    static int[] fArr = new int[MAX_VALUE];

    public static void main(String[] args){
        int[] arr = new int[]{1,1,3,2,4,5,6};
        System.out.println("Original array:    "+toString(arr));
        int[][] leftRight = lesserLeftRight(arr);
        System.out.println("Lesser left count: "+toString(leftRight[0]));
        System.out.println("Greater right cnt: "+toString(leftRight[1]));
    }

    public static String toString(int[] arr){
        String result = "[";
        for(int num: arr){
            if(result.length()!=1){
                result+=", ";
            }
            result+=num;
        }
        result+="]";
        return result;
    }

    public static void reset(){
        Arrays.fill(fArr,0);
    }

    public static void update(int idx, int val){
        while(idx < MAX_VALUE){
            fArr[idx]+=val;
            idx += (idx & -idx);
        }
    }

    public static int cntSum(int idx){
        int result = 0;
        while(idx > 0){
            result += fArr[idx];
            idx -= (idx & -idx);
        }
        return result;
    }

    public static int[] lesserLeftCount(int[] arr){
        reset();
        int[] result = new int[arr.length];
        for(int i=0; i<arr.length; i++){
            result[i] = cntSum(arr[i]-1);
            if(cntSum(arr[i])==result[i]) update(arr[i],1);
        }
        return result;
    }

    public static int[][] lesserLeftRight(int[] arr){
        int[] left = new int[arr.length];
        int min = Integer.MAX_VALUE;
        for(int i=0; i<arr.length; i++){
            left[i] = arr[i];
            if(min>arr[i]) min=arr[i];
        }
        for(int i=0; i<arr.length; i++) left[i]+=min+1;
        left = lesserLeftCount(left);

        int[] right = new int[arr.length];
        int max = Integer.MIN_VALUE;
        for(int i=0; i<arr.length; i++){
            right[i] = arr[arr.length-1-i];
            if(max<right[i]) max=right[i];
        }
        for(int i=0; i<arr.length; i++) right[i] = max+1-right[i];
        right = lesserLeftCount(right);
        int[] rightFinal = new int[right.length];
        for(int i=0; i<right.length; i++) rightFinal[i] = right[right.length-1-i];
        return new int[][]{left, rightFinal};
    }
}

同じ結果が得られます。

于 2013-09-25T07:12:35.730 に答える
2

RMQ の解決に使用されるセグメント ツリー データ構造を試してください。正確に n log n になります。

そして、一般的にRMQの問題を調べてください。あなたの問題はそれに縮小されるかもしれません。

于 2013-09-24T23:16:09.630 に答える