计算已排序数组中数字的出现次数 [英] Count the number of occurrences of a number in a sorted array

问题描述

我的老师给了我下一个任务：

My teacher gave me the next task:

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;
}

SearchLeft 和 SearchRight 迭代数组，直到数字没有显示。

SearchLeft and SearchRight iterate the array, until the number doesn't show.

我不确定我是否已经写完了这个问题的代码更快，我希望看到其他意见。

I'm not sure if I have achieved writing the faster code for this problem, and I would like see other opinions.

编辑：在评论和答案的帮助下，这是我的当前尝试：

After some help from comments and answers, this is my current attempt:

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;
}

推荐答案

SearchLeft和SearchRight迭代数组，直到数字没有显示。

SearchLeft and SearchRight iterate the array, until the number doesn't show.

这意味着如果整个数组都填满了目标值，你的算法是 O（n）。

That means if the entire array is filled with the target value, your algorithm is O(n).

你可以使它 O（ log n）最糟糕的情况，如果你二元搜索 x 的第一次和最后一次出现。

You can make it O(log n) worst case if you binary-search for the first and for the last occurrence of 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);

这篇关于计算已排序数组中数字的出现次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！