问题:输入是一个(不一定是排序的)序列S = k1,k2,...,n个任意数的kn.考虑形式为min {ki,kj}的n 2个数的集合C,对于1 <= i,j <= n.提出一个O(n)时间和O(n)空间算法来找到C的中位数.
到目前为止,通过检查C的不同集合S,我发现C中S中最小数字的实例数等于(2n-1),下一个最小数字:(2n-3),依此类推,直到你只有一个最大数字的实例.
有没有办法使用这些信息来找到C的中位数？
问题:两组A和B各有n个元素.假设每个元素是[0,n ^ 100]范围内的整数.这些集合不一定排序.演示如何在O(n)时间内检查这两个集是否不相交.您的算法应使用O(n)空间.
我对此问题的最初想法是创建集合A的哈希表,并为B中的每个元素搜索此哈希表.但是,我不知道有任何方法来创建具有此范围的数据集的哈希表只需要O(n)空间.我应该考虑一种完全不同的方法吗？
更新:我联系了教授,询问有关实现哈希表的问题,他的回答是:请注意,哈希只能平均花费O(1)时间.对于这个问题,我们需要最坏情况的O(n)时间算法.
所以似乎问题是寻找一种不同的方法......