计算已排序数组中数字的出现次数
我的老师给了我下一个任务：
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 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 value) { high = middle; } else { low = middle + 1; } } return low; }
SearchLeft和SearchRight迭代数组，直到数字不显示。
这意味着如果整个数组都填充了目标值，则算法为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);
那么这基本上是二元搜索+走向解决方案区间的边界。 唯一可能加快速度的方法就是缓存最后的低值和高值，然后使用二进制搜索来找到寄存器，但这实际上只对非常大的时间间隔有影响，在这种情况下你跳不太可能进入它。