是否有可能重写代码，使时间复杂度为O(nlogn)？
是否有可能重写代码，使时间复杂度为O(nlogn)？
提问于 2019-10-16 22:36:53
我想找出数组中两个数字之间的最大差，每分钟必须在减法器之前。例如:在数组(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)。
回答 3
Stack Overflow用户
回答已采纳
发布于 2019-10-17 00:02:30
将数组从最后一个元素遍历到第一个元素。
保持两个变量的答案和最小值。
For each element i:
answer=max(answer,i-mintillnow)
mintillnow=min(mintillnow,i)最后的答案可以在遍历结束时的answer中找到。
时间复杂度:- O(n)
如果出于某种原因，您希望它恰好是O(log(n)):-
维护一个Min堆和一个应答变量。
在每一步，
查询Min堆到现在为止最小的元素，并从当前元素中减去它，并检查它是否大于答案变量。
将当前元素推入Min堆中。
插入到Min堆中需要O(log(n))
查询最小值需要O(1)。
总时间复杂度:- O(n log(n))
Stack Overflow用户
发布于 2019-10-16 22:45:12
看起来，您想要找到数组中任意两个数字之间的最大差异。
您认为有什么方法可以比数组中的最小数和最大数之间的差异更大吗？(我不这么认为)
如果没有，那么您可以用O(n)编写它:只需循环一次数组，以找到最小和最大的数目；它们之间的差异应该是最大的差异。
Stack Overflow用户
发布于 2019-10-16 22:44:22
你能先对数组进行排序吗？这将是o(nlgn)。第一个和最后一个之间的差异将是最大的差异？
Arrays.sort(D);
return D[D.length - 1] - D[0];页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58422554
复制相关文章
相似问题
腾讯云开发者
