6

私の先生は私に次の仕事をくれました：

On a sorted array, find the number of occurrences of a number.
The complexity of the algorithm must be as small as possible.

これは私が考えたことです：

public static int count(int[] a, int x)
{
    int low = 0, high = a.length - 1;

    while( low <= high )
    {
        int middle = low + (high - low) / 2;

        if( a[middle] > x ) {
            // Continue searching the lower part of the array
            high = middle - 1;
        } else if( a[middle] < x ) {
            // Continue searching the upper part of the array
            low = middle + 1;
        } else {
            // We've found the array index of the value
            return x + SearchLeft(arr, x, middle) + SearchRight(arr, x, middle);
        }
    }

    return 0;
}

SearchLeftSearchRight番号が表示されなくなるまで、配列を繰り返します。

この問題に対してより高速なコードを書くことができたかどうかはわかりません。他の意見を聞きたいと思います。

編集：コメントと回答からのいくつかの助けの後、これは私の現在の試みです：

public static int count(int[] array, int value)
{
    return SearchRightBound(array, value) - SearchLeftBound(array, value);
}

public static int SearchLeftBound(int[] array, int value)
{
    int low = 0, high = array.length - 1;

    while( low < high )
    {
        int middle = low + (high - low) / 2;

        if(array[middle] < value) {
            low = middle + 1;
        }
        else {
            high = middle;
        }
    }

    return low;
}

public static int SearchRightBound(int[] array, int value)
{
    int low = 0, high = array.length - 1;

    while( low < high )
    {
        int middle = low + (high - low) / 2;

        if(array[middle] > value) {
            high = middle;
        }
        else {
            low = middle + 1;
        }
    }

    return low;
}
4

2 に答える 2

10

SearchLeft と SearchRight は、数値が表示されなくなるまで配列を繰り返します。

つまり、配列全体がターゲット値で満たされている場合、アルゴリズムはO(n).

O(log n)の最初と最後の発生をバイナリ検索すると、最悪のケースになる可能性がありxます。

// search first occurrence
int low = 0, high = a.length - 1;
while(low < high) {
    int middle = low + (high-low)/2;
    if (a[middle] < x) {
        // the first occurrence must come after index middle, if any
        low = middle+1;
    } else if (a[middle] > x) {
        // the first occurrence must come before index middle if at all
        high = middle-1;
    } else {
        // found an occurrence, it may be the first or not
        high = middle;
    }
}
if (high < low || a[low] != x) {
    // that means no occurrence
    return 0;
}
// remember first occurrence
int first = low;
// search last occurrence, must be between low and a.length-1 inclusive
high = a.length - 1;
// now, we always have a[low] == x and high is the index of the last occurrence or later
while(low < high) {
    // bias middle towards high now
    int middle = low + (high+1-low)/2;
    if (a[middle] > x) {
        // the last occurrence must come before index middle
        high = middle-1;
    } else {
        // last known occurrence
        low = middle;
    }
}
// high is now index of last occurrence
return (high - first + 1);
于 2012-12-30T21:43:11.457 に答える
2

これは本質的に二分探索 + 解間隔の境界に向かって歩くことです。これを高速化できる唯一の方法は、おそらく低値と高値の最後の値をキャッシュし、バイナリ検索を使用してボーダーを見つけることですが、これは実際には非常に長い間隔でのみ問題になり、ジャンプした可能性は低いですその中に。

于 2012-12-30T21:40:33.100 に答える