栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

通过a * b的结果对(a,b)对进行排序

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

通过a * b的结果对(a,b)对进行排序

只要

C(m)
如此神奇,您就不能使用任何更好的技术来直接找到您的解决方案,因此您确实需要以
a*b
递减的顺序遍历所有内容,这就是我要做的:

用所有对初始化一个max-heap,

(a, b)
使
a = b
。这意味着堆包含
(0, 0), (1, 1), ... , (1.000.000,1.000.000)
。堆应该基于该
a * b
值。

现在不断:

  1. (a, b)
    从堆中获取最大对。
  2. 验证是否
    (a, b)
    满意
    C(a * b)
    。如果是这样,您就完成了。
  3. 否则,添加
    (a, b-1)
    到堆中(已提供
    b > 0
    ,否则什么也不做)。

这是一个非常简单的

O(n log n)
时间和
O(n)
空间算法,只要您能够快速找到答案(几次迭代)即可。这当然取决于
C


如果遇到空间问题,您当然可以通过将问题分成多个子问题来轻松地降低空间复杂度,例如2:

  1. 只添加
    (500.000, 500.000), (500.001, 500.001), ... , (1.000.000, 1.000.000)
    到堆中,找到最合适的一对
    (a, b)
  2. 对进行相同操作
    (0, 0), (1, 1), ... (499.999, 499.999)
  3. 采取两种解决方案中最好的一种。


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/650017.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号