需要从给定范围(x，y(中查找排序后的ArrayList中元素的计数。如果计数在 ArrayList 中，则计数也应该具有范围元素的计数。
因此，我通过遍历整个列表并获取计数来做到这一点。
伪代码：
count = 0;
for (i=0; i<length(list); i++)
{
if (list[i]>= startrange and list[i]<=endrange)
{
count = count+1;
}
}
当前解决方案需要更多时间，因为输入数组大小超过 1000000。帮助我优化解决方案。
例：
输入数组如下所示[1,4,5,8,9,12,16,19,23,26,28,29,30,31,33,35,37]。
输入范围：(12,30(
输出应类似于8
你说需要从给定的范围(x，y(中找到排序的ArrayList中的元素计数。
因此，您可以利用binary search来提高代码效率。
-
在二分搜索中，我们首先有 2 个指针，比如
low和high.现在，我们从此范围内的中间元素开始搜索。如果中间元素小于所需的元素，我们移动到范围的右侧(mid + 1,high)，否则我们移动到范围的左侧(low,mid-1)。 -
在这种特殊情况下，我们必须进行 2 次二叉搜索。让我们以
(12,30)为例。一种是找到具有12的最低索引，另一种是二分搜索以找到具有30的最高索引。此查询的答案将是highestIndex - lowestIndex + 1。
片段：
public class Main{
public static void main(String[] args) {
int[] arr = {1,4,5,8,9,12,16,19,23,26,28,29,30,31,33,35,37};
int[][] queries = {
{12,30},
{-1,37},
{1,49}
};
for(int[] q : queries){
System.out.println(binarySearch(arr,q[0],q[1]));
}
}
private static int binarySearch(int[] arr,int low,int high){
return highestIndex(arr,high) - lowestIndex(arr,low) + 1; // + 1 because of 0-based indexing
}
private static int highestIndex(int[] arr,int num){
int low = 0 , high = arr.length - 1;
while(low <= high){
int mid = low + (high - low) / 2; // (or (low + high)/2, as it doesn't matter in this context
if(arr[mid] <= num) low = mid + 1;
else high = mid - 1;
}
return high;
}
private static int lowestIndex(int[] arr,int num){
int low = 0 , high = arr.length - 1;
while(low <= high){
int mid = low + (high - low) / 2; // (or (low + high)/2, as it doesn't matter in this context
if(arr[mid] >= num) high = mid - 1;
else low = mid + 1;
}
return low;
}
}
演示：https://onlinegdb.com/BJ4g3AXXL
- 以上代码的空间复杂度
O(1)。 - 上述代码的时间复杂度渐近
O(Q * (log(N) + log(N)))~O(Q * 2 * log(N))~O(Q * log(N))，其中Q是查询数，N是数组的大小。
遵循Java 8 Stream单行代码将正常工作并按预期返回结果，而无需使用繁琐的for循环。
int[] xyz = { 1, 4, 5, 8, 9, 12, 16, 19, 23, 26, 28, 29, 30, 31, 33, 35, 37 };
long elementCountWithinRange = Arrays.stream(xyz).filter(x -> (x > 12 && x <= 31)).count();
System.out.println(elementCountWithinRange); // will return 8
注意：@Gaurav Dhiman之前给出的类似答案是不正确的，因为表达式不会编译为 count(( 方法返回long而不是int。另外，即使您解决它也会给出以下错误：
The operator >= is undefined for the argument type(s) int[], int
为了解决我使用Arrays.stream()而不是Stream.of()来创建流的问题。
int cnt=Stream.of(arr).filter(o->(o>=12&& o<=30)).count();