- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我的问题陈述是这样的 -查找排序数组中小于给定数字的数字的计数,这应该在时间上有效地完成。我编写了一个使用二分搜索的程序来获取计数,但从时间复杂度角度来看它失败了。需要帮助来实现这一目标。
import java.util.Arrays;
public class SortedSearch {
public static int countNumbers(int[] sortedArray, int lessThan) {
if(sortedArray.length ==1 || sortedArray.length == 0) {
return singleElement(sortedArray, lessThan);
}
else {
return binarySearch(sortedArray, lessThan);
}
}
public static int singleElement(int[] sortedArray, int searchVal) {
if(sortedArray.length == 0) {
return 0;
}
if(sortedArray[0] < searchVal) {
return 1;
}
return 0;
}
private static int binarySearch(int[] sortedArray, int searchVal) {
int low = 0;
int high = (sortedArray.length)-1;
int mid = (low + high)/2;
if((sortedArray.length == 0) || (sortedArray[0] > searchVal)) {
return 0;
}
if(sortedArray[high] < searchVal) {
return sortedArray.length;
}
if(sortedArray[high] == searchVal) {
return sortedArray.length-1;
}
if(sortedArray[mid] < searchVal) {
int newLow = low;
int newHigh = calculateNewHigh(sortedArray, newLow, 0, searchVal);
int[] newArray = Arrays.copyOfRange(sortedArray, newLow, newHigh+1);
return newArray.length;
}
else {
int newLow = low;
int newHigh = mid;
int[] newArray = Arrays.copyOfRange(sortedArray, newLow, newHigh+1);
return binarySearch(newArray, searchVal);
}
}
private static int calculateNewHigh(int[] sortedArray, int low, int previousHigh, int searchVal) {
int newHigh = previousHigh + (sortedArray.length-low)/2;
if(sortedArray[newHigh] < searchVal) {
newHigh = calculateNewHigh(sortedArray, newHigh, newHigh, searchVal);
}
if(sortedArray[newHigh] == searchVal) {
newHigh--;
}
if(sortedArray[newHigh] > searchVal) {
newHigh--;
}
return newHigh;
}
public static void main(String[] args) {
System.out.println(SortedSearch.countNumbers(new int[] { 1, 3, 5, 7 }, 4));
}
}
最佳答案
既然你无论如何都在使用Arrays
,那就不要使用Arrays.binarySearch(int[] a, int key)
方法,而不是尝试编写自己的方法?
public static int countNumbers(int[] sortedArray, int lessThan) {
int idx = Arrays.binarySearch(sortedArray, lessThan);
if (idx < 0)
return -idx - 1; // insertion point
while (idx > 0 && sortedArray[idx - 1] == lessThan)
idx--;
return idx; // index of first element with given value
}
while
循环1是必要的,因为javadoc说:
If the array contains multiple elements with the specified value, there is no guarantee which one will be found.
1) 如果例如,此循环不是最佳循环所有值都相同,请参见例如Finding multiple entries with binary search
关于java - 使用二分查找高效地获取排序数组中小于给定数字的数字计数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59441449/
问题:如果联接表的属性大于/小于值,是否可以在散列条件下进行测试 例如:测试 Actor 年龄是否大于年龄变量: 是否可以写而不是 ARRAY CONDITION 的: ageVariable = 3
这个问题已经有答案了: How to check if a number is between two values? (12 个回答) 已关闭 6 年前。 我目前正在 Codecademy 上学习
我想知道是否有一种方法可以比较 arrayList 中的连续元素。我有这个 for (int j=0; j< Index.size(); j++) { if(Index.get(j) < Ind
我正在压缩一些代码,现在我有 4 种方法,它们几乎都做同样的事情,除了 for 循环的建模有点不同。我正在传递 int 的 up , down , right ,和left作为这个紧凑方法的参数,这与
SELECT DISTINCT s.sname, s.sid FROM student s, class c WHERE s.programme = 'CS' AND s.level = '2' AN
我正在尝试通过命令行读取文件名, 这是教授要我们输入的命令: java MultiBinaryClient xxxxxx.edu 6001 < files.txt 我正在尝试使用 args[3]获取文
在 C# 中,您可能会看到以下内容: [] 或类似的行(但没有大于/小于符号): [assembly: AssemblyTitle("MyProject")] 我知道第一个称为属性(它有 gt 和 l
我只是想知道大于/小于的结果是如何计算并返回给高级语言的。 我在这里寻找硬件门模型。 让我们用一个统一的例子来解释,比如说5 > 3。 最佳答案 它通常通过带有进位检测的减法来实现。 从门控的角度来看
这个问题在这里已经有了答案: strange output in comparison of float with float literal (8 个答案) 关闭 8 年前。 案例一 float
你到底如何检查一个数字属性是否小于 Apache Ant? 从我所看到的(我是 Ant 的新手)你只能做 ? 最佳答案 您可以使用 (见 http://ant.apa
在 C 中使用 float.h 我想知道如何找到最大的数字,如果我加到 1,答案将保持为 1。 即 1 + x = 1 如何找到 x? 最佳答案 如果你想要“小于 FLT_EPSILON 的最大数字”
我正在尝试查询节点统计信息端点(_nodes / stats)并收到此错误: {"error":{"root_cause":[{"type":"illegal_argument_exception",
有没有更快的方法来检查列表中的项目是否大于、小于或等于某个数字? 或者你只需要循环它?我只是好奇是否有为此预先构建的函数。 示例: 列表包含 5、5、10、15、15、20。 我想检查是否有多少个
因此,我必须编写一个代码,从用户那里获取 2 个日期(月/日/年),如果第一个日期小于第二个日期,则返回“true”。在任何其他情况下,日期将为“假”或“它们是相同的”。我被告知我不能要求用户执行指定
我有两个变量,如果它们的值彼此相差在 5 个数字以内,我想触发一些代码。不知道哪个变量具有更高的值,我可以这样做: if (var1 > var2) { if ((var1 - var2) < 5
我有一个函数,它接受一个对象并将其转换为字节数组: public static byte[] serialize(Object obj) throws IOException { try(By
下载大小已经低于 4MB 的应用程序是否也可以作为免安装应用程序未经修改地分发? 最佳答案 要将该应用程序作为免安装应用程序提供,仍需采取一些步骤。参见 http://g.co/instantapps
我有以下 SELECT 但无法正常工作: SELECT COUNT(userid) FROM login WHERE 17 YEAR(DATE_SUB(NOW(), INTERVAL TO_DAYS
我制作了一个脚本,其中 #hsz-wrap2 附加到最后一个可见的 div,当 div 数量低于或等于 16 在 #snapshot_vertical div 内。 但是,if 条件的工作方式我不明白
我在外部的一排内放置了一个 Logo 、一个搜索框和一个语言栏,并位于 Bootstrap 导航栏上方。这一行当然仍在主容器中,但它包含我提到的 3 个元素——我和我的客户认为这 3 个元素独立于导航
我是一名优秀的程序员,十分优秀!