java - 下一个大元素的时间复杂度
问题描述
参考GeeksforGeeks的这个问题,我已经解决了 Next Greater Element 问题。我很困惑找到以下问题的时间复杂度(Big O)。如果有人可以帮助我,那将非常有帮助。
问题:给定一个数组,打印每个元素的下一个更大元素 (NGE)。元素 x 的下一个更大元素是数组中 x 右侧的第一个更大元素。对于不存在更大元素的元素,将下一个更大元素视为-1。
例子:
a) 对于任何数组,最右边的元素总是有下一个更大的元素为 -1。
b) 对于按降序排序的数组,所有元素的下一个较大元素为 -1。
这是解决这个问题的可接受方法吗?
int[] array = {20,10,5,3}; int len =array.length; int[] temp = new int[len]; int j=0; int i=j; while(j<len-1){ ++i; if(i>=len){ System.out.println(array[j]+"----> -1"); j++; i=j; continue; } if(array[j]<array[i]){ System.out.println(array[j]+"----> "+array[i]); j++; i=j; } } System.out.println(array[j]+"----> -1");
解决方案
您在决定算法的复杂性时遇到了困难,因为您正在使用continue
,这给您的推理增加了不必要的困难。
重写为以下内容(不使用break
or continue
):
public void test() {
int[] array = {10, 20, 3, 5};
int len = array.length;
for (int j = 0; j < len - 1; j++) {
int nge = -1;
for (int i = j + 1; i < len && nge < 0; i++) {
if (array[j] < array[i]) {
nge = array[i];
}
}
System.out.println(array[j] + "----> " + nge);
}
System.out.println(array[len-1] + "----> -1");
}
现在很清楚,这是O(n lg n)
因为外部循环迭代到n
,内部循环最多n - j
。
推荐阅读
- javascript - 嵌套数组中的 lodash 选择
- angular - 如何以角度 2 从订阅者下一个方法返回数据
- listview - 单击javafx时Listview删除项目
- c - 使用CLion2018或VS2015构建无依赖的C项目
- excel - 从 Excel 表格创建 Word 文档
- twitter-bootstrap - 在一行中正确对齐 div
- neo4j - Neo4j中对密码查询的误解
- c# - 如何在操作委托中使用 Lambda 设置多个属性
- javascript - 在输入字段中输入@后如何获取下拉列表?
- selenium - org.openqa.selenium.interactions.Actions 中的 java.lang.NullPointerException。