1

在Java中，如果我想从数组中获取特定范围内的元素，那么最有效的方法是什么？

例如

大批

A = [25,32,54,23,76,34];

我想得到

element between 45 and 55.

那就是元素：

54

那么获得它的最有效方法是什么？

4

5 回答 5

3

如果您要重复搜索数组，那么您最好的选择是对数组进行排序并使用二进制搜索来查找下限和上限。当分摊到足够多的搜索时，这将为您提供 O(log n) 性能。

如果它是一次性搜索，那么除了扫描数组并将每个元素与其他人建议的下限/上限进行比较之外，您最好的方法就是 - 这是 O(n)。

于 2012-11-01T05:35:10.620 回答
0

你可以试试这样的

int dLimit=45, uLimit =55, result[] = new int[A.length],j=0;
for(int i : A){
    if(i>dLimit && i<uLimit)
        result[j++] = i;
}
于 2012-11-01T05:10:04.187 回答
0

我不确定这是否是最有效的，但我会做这样的事情。

    int[] rangeTracker = new int[100];
int rangeTrackIndex = 0;
For (int j = 0; j < A.getLength(); j++) {

     if ((A[j] >= 45) && (A[j] <= 55)) {
          rangeTracker[rangeTrackIndex] = A[j];
          rangeTrackIndex++;
}
}
For (int j=0; j < rangeTracker.getLength(); j++) {
     System.out.println(rangeTracker[j]);
}

我的一些语法可能是错误的，这可能是错误的方法，但我只使用 Java 大约 2 个月。此外，我只从事编程工作大约 4 个月。我希望这有帮助。

于 2012-11-01T05:18:44.280 回答
0

它需要最小的 O(n) 复杂度，因为为了知道给定游侠之间有多少元素，我们必须至少遍历所有元素一次，因为有 n 个元素，我们计算 n 次比较，所以复杂度是 O(n)

来到解决方案 AFAIK 。

n<-array.length;

for(int i=0;i<n;i++)
{
  if((a[i]<upperLimit) && (a[i]>lowerLimit))
   {
      SOP(a[i]);//or store in temp array based on your requirement
   } 
}
于 2012-11-01T05:22:19.700 回答
0

您必须知道数组中有哪些元素才能回答您的查询（a 和 b 之间的元素）。

如果您要回答 n 个这样的查询，那么您可能可以对数组进行排序 (n log n)，然后找到大于或等于 a 的最近元素（a 小于 a 和 b）和小于或的最近元素通过使用二进制搜索 (n log n + n log n) 等于 b，然后检索它们之间的元素。

如果 a 和 b 之间的元素数量很小，您可能会在 n 个查询上实现 O(n log n) 复杂度，使每个查询的平均价值约为 O(log n) 但如果 a 和 b 之间的元素数量为n 的顺序，每个查询将值得 O(n) 复杂度。

于 2012-11-01T05:35:43.927 回答