2

次のクラスの配列がyの昇順で並べ替えられているとします。

public class Obj {
    public int x;
    public int y;
}

ログ（N）時間で指定された最小および最大範囲内のy値を持つ配列内のObjアイテムの数を見つけるにはどうすればよいですか？

二分探索を使用して、binarySearchと減算で最小要素と最大要素の位置を見つけることを考えましたが、2回検索しているので、2 log（n）ではないでしょうか。

public static int getNumberOfItems(Obj[] a, int min, int max) {
4

3 に答える 3

4

時間内に何かをするように求められた場合log(n)、これは通常、を意味しO(log(n))ます。

この場合、注意する価値がO(2 log(n)) == O(log(n))あります。つまり、2つは同じものです。

big-oh表記の詳細については、ウィキペディアのページを参照してください。

于 2013-03-06T09:05:24.807 に答える
1

ビン検索はそのアプローチに適しています。O（logN）はc * log Nを意味します。
したがって、ビン検索は問題ありませんが、範囲（minFoundIndex、N）のsearchomgによってmaxIndexsearchimgのビン検索呼び出しを最適化できます。

于 2013-03-06T09:14:57.043 に答える
0

この質問は、O（logn）の実装を行ったここと同じです。

アイデアは、下限と上限の範囲二分探索によるものです。あなたの例では、すべての値がy値について話している。

  1. 下限（左側の範囲）の場合、次の関数を呼び出して、値がそれ以上のソート済み配列のインデックスを取得できます。それ以外の場合は-1です。

    int binarySearchForLeftRange(int a[], int length, int left_range)
{
    if (a[length-1] < left_range)
        return -1;

    int low = 0;
    int high = length-1;

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

        if(a[mid] >= left_range)
            high = mid-1;
        else //if(a[mid]<i)
            low = mid+1;
    }

    return high+1;
}

  2. 上限（右の範囲）の場合、次の関数を呼び出して、値がそれよりも小さいか等しいソートされた配列のインデックスを取得できます。それ以外の場合は-1です。

    int binarySearchForRightRange(int a[], int length, int right_range)
{
    if (a[0] > right_range)
        return -1;

    int low = 0;
    int high = length-1;

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

        if(a[mid] > right_range)
            high = mid-1;
        else //if(a[mid]<i)
            low = mid+1;
    }

    return low-1;
}

  3. 最後に、この範囲内の要素の数を取得したい場合は、上記の2つの関数の戻り値に基づいて簡単に実行できます。

    int index_left = binarySearchForLeftRange(a, length, left_range);
int index_right = binarySearchForRightRange(a, length, right_range);

if (index_left==-1 || index_right==-1 || index_left>index_right)
    count = 0;
else
    count = index_right-index_left+1;

テスト:(重複あり）

    int a[] = {1,2,4,4,5,8,12,15,15,23,54};
    int length = sizeof(arr)/sizeof(arr[0]);

    int left_range = 4;
    int right_range = 15;
    int index_left = binarySearchForLeftRange(a, length, left_range); // will be 2
    int index_right = binarySearchForRightRange(a, length, right_range); // will be 8

    int count; // will be 7
    if (index_left==-1 || index_right==-1 || index_left>index_right)
        count = 0;
    else
        count = index_right-index_left+1;
于 2013-12-20T12:52:15.287 に答える