V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
PepperEgg
V2EX  ›  C++

c++面试题,数字范围包含关系判断。

  •  
  •   PepperEgg · 2021-11-04 14:36:32 +08:00 · 1655 次点击
    这是一个创建于 1118 天前的主题,其中的信息可能已经有所发展或是发生改变。
    C++
    给定一个 list<int> , 例如{1 ,21 ,55 ,99 ,111 ,10000 ,99999} 随机,依次递增。
    再给定一个 list<pair<int, int> > 数据为 {( 1 ,8 ),( 10 ,20 ),( 27 ,100 )} 随机,依次递增,每个 pair 不存在交集。中间可以有空缺。

    假定两列数据都大于 100w 条,如何快速列出第一个列表的数字存在于第二个列表中。
    比如 1 ,就属于(1,8),55 属于( 27 ,100 ),21 则不属于;
    有无最优解,求问大佬。
    8 条回复    2021-11-05 08:44:54 +08:00
    iBugOne
        1
    iBugOne  
       2021-11-04 14:45:04 +08:00
    都排好序了还不直接扫描😅

    用归并排序中「归并一轮」这个操作的思路,你马上就知道第一个 list 里哪些数是夹在第二个 list 哪些数中间了
    zidian9
        2
    zidian9  
       2021-11-04 14:57:11 +08:00
    从前往后扫描,复杂度 O(m+n)
    JKeita
        3
    JKeita  
       2021-11-04 15:00:03 +08:00
    双指针遍历不就行了?
    JKeita
        4
    JKeita  
       2021-11-04 15:03:51 +08:00
    i:第一个列表指针
    j:第二个列表指针

    三种情况
    v < min(j): i++
    v >= min(j) && v <= max(j): i++
    v > max(j): j++
    Mirage09
        5
    Mirage09  
       2021-11-04 15:18:22 +08:00
    第二个列表如果排序了那就 binary search 找呗,最多是 mlogn
    Jooooooooo
        6
    Jooooooooo  
       2021-11-04 15:20:17 +08:00
    两个指针往前挪
    stcheng
        7
    stcheng  
       2021-11-04 15:25:57 +08:00
    1. 双指针 O(m+n)
    2. 二分搜索 O(m*log(N)) or O(n*log(m))
    根据 m 和 n 大小做选择
    byaiu
        8
    byaiu  
       2021-11-05 08:44:54 +08:00 via iPhone
    list 不能随机存取吧……
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5590 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 21ms · UTC 06:37 · PVG 14:37 · LAX 22:37 · JFK 01:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.