2

指定された数値の配列から、指定された数値の前任者を見つける方法は? たとえば、指定された配列に が含まれ てい-2,1,0,3
て、入力番号が0の場合、先行は-2です。

次のコードを書きました。

public static int getPredecessor(int[] inpArr, int key) {
    int minDiff = key<=0 ? (key-inpArr[0]) : key;
    int predecessor = key;
    for(int i=0;i<inpArr.length;i++) {
        if(inpArr[i] < key && (key - inpArr[i])<=minDiff)
        {
            minDiff = key - inpArr[i];
            predecessor = inpArr[i];
        }   
    }
    return predecessor;
}

私が行ったことは、基本的に、提供された数値と配列内の各数値との最小の違いを追跡することです。最小の差が検出されるたびに、配列内のその特定の番号が前任者として格納されます。最後の return ステートメントが入力数値と同じ数値を返す場合は、指定された配列に先行ステートメントが見つからなかったことを意味します。

私の質問は次
のとおりです。コードを何らかの方法で最適化できますか? O(n) 時間と O(1) 空間の複雑さで実行されます。

4

2 に答える 2

2

ソートされていない配列（配列の例のように）に対する単一のクエリの場合、配列内のすべての要素との比較が必然的に必要になるため、O（N）時間が達成できる最善の時間です。

配列を最初に並べ替えるとO（N log N）時間かかりますが、配列に対して多くのクエリが予想される場合は、各クエリをO（log N）時間の二分探索で実行できます。したがって、十分なクエリがある場合、クエリの平均コストはO（N）よりも低くなる可能性があります。

あるいは、多くのクエリが同じ小さな（っぽい）キー値のセットを使用すると予想される場合、たとえばハッシュテーブルを使用して各キーの結果をメモすると、最終的にはクエリごとの平均O（1）パフォーマンスが得られます。 O（N）スペースのコスト。

于 2013-02-15T02:38:01.780 に答える
0

上記のコードは、inpArr = [-5、-2]やkey = -4、inpArr = [-5、-2、-3]、key =+1のような場合には機能しません。だからそれを修正しました。修正されたコードは次のとおりです。

public static int getPredecessorv2(int[] inpArr, int key) {
    int minDiff = Math.abs(key);
    int pred = key;
    if(inpArr[0] < key) {
        minDiff = key - inpArr[0];
        pred = inpArr[0];
    } 
    for(int i=0;i<inpArr.length;i++) {
        if(inpArr[i] < key && (key - inpArr[i])<=minDiff)
        {
            minDiff = key - inpArr[i];
            pred = inpArr[i];
        }   
    }
    return pred;
}
于 2013-02-23T20:38:05.610 に答える