我的老师给我下一个任务:
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
迭代数组,直到数字不显示为止。
我不确定我是否已经为这个问题编写了更快的代码,我希望看到其他意见。
编辑在评论和答案的帮助下,这是我目前的尝试:
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 and SearchRight iterate the array, until the number doesn't show.
这意味着如果整个数组都充满了目标值,则您的算法是O(n)
。
如果您对 x
的第一次出现和最后一次出现进行二分搜索,您可以将它设为 O(log n)
最坏情况。
// 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);
关于java - 计算一个数字在排序数组中出现的次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14094914/