我已经引用 this 解决了下一个更大元素问题来自 GeeksforGeeks 的问题。我很困惑找到以下问题的时间复杂度(大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");
最佳答案
您很难决定算法的复杂性,因为您使用的是继续
,这给您的推理增加了不必要的困难。
重写为以下内容(不使用 break
或 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
.
关于java - 下一个更大元素的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51074608/