我想找出数组中两个数字之间的最大差值,被减数必须在减法器之前。例如:在一个数组(3,1,5,4,2)中,最大差应该是3(5-2)。在数组(100, 3 ,200)中,最大差应该是97(100-3)。
int max = 0, diff;
for(int i = 0; i<n; i++){
for(int j = i+1; j < n; j++){
diff = D[i] - D[j];
if(diff > max)
max = diff;
}
}
return max;
我知道它的时间复杂度为 O(n^2)
但我希望它正好是 O(nlogn)
。
最佳答案
从最后一个元素到第一个元素遍历数组。
维护两个变量 answer 和 mintillnow。
For each element i:
answer=max(answer,i-mintillnow)
mintillnow=min(mintillnow,i)
最终答案可以在遍历结束时的answer
中找到。
时间复杂度:- O(n)
如果出于某种原因你希望它正好是 O(log(n)):-
维护一个最小堆和一个答案变量。
在每一步,
查询最小堆中的最小元素,然后从当前元素中减去它,并检查它是否大于答案变量。
将当前元素压入最小堆。
插入最小堆需要 O(log(n))
查询最小值需要 O(1)。
总时间复杂度:- O(n log(n))
关于java - 是否可以重写代码使时间复杂度为 O(nlogn)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58422554/