小编Kan*_*shk的帖子

给定两个大小为N的未排序数组,我们将确定从它们构造的二进制搜索树是否相等.

因此,数组的元素被选中并插入到基本(无平衡,无红黑,无任何)二叉搜索树中.直接给出两个数组,我们可以确定它们是否会产生相同的二进制搜索树.

有一个明显的O(N ²)最坏情况时间复杂度解决方案:构造两棵树,并比较它们的相等性.

是否有O(N)或O(N log N)解决方案？

我试图提取的问题的想法是:BST的构造取决于元素的相对位置.例如,如果在一个数组中有一个紧邻20的值为51的元素,则在另一个数组中必须没有20到51之间的元素才能使树相等(否则20的右子将是该数字,而不是51 ).

我尝试了几种方法:

1. 天真的方法:构建2棵树并进行比较.
2. 我使用了一个有趣的变体,我将数组分成2个(一个较小的子数组和一个比数组大的子数组),并递归地将左数组传递给左子,另一个传递给右.就地和厚脸皮,但仍然是O(N ²).
3. 一位朋友尝试将最长的子序列应用于它并找到它然后进行比较,但这是不正确的.
4. 我正在试图用LinkedHashMap解决它,但我很难证明它的正确性.

帮助,以及解决这个问题的任何提示将非常感激.

问题如下: -

给你N个不同大象的生命时间,表示为一对整数.

恩.[5,10] [6,15] [2,7]意味着,一只大象从5年级到10年级生活.第二只大象从6年级到15年级,依此类推.

您可以假设大象最多只能活M年.(不是问题的一部分,但我们可能需要它来表示算法的复杂性.)

根据这些数据,找出最大数量的大象居住的年份.任意解决关系.

我已经尝试了几种方法,但没有任何实质性的东西可以打败天真的解决方案的复杂性.天真的解决方案是: -

1. Maintain an array(call it ctr).
2. For every set you encounter, 
    increment all values of ctr in that range.
3. Once you have traversed all sets, 
    find the index with the highest value in ctr.

很容易看出复杂性将是O(N*M).

有人能提供更好的解决方案吗？

另一个问题是:是否存在可以在O(1)时间内更改值范围的数据结构？在数组中,要修改k个元素,您显然需要O(k)时间.还有什么更好的？