这是一个创建于 1503 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 则不属于；
有无最优解，求问大佬。
给定一个 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 则不属于；
有无最优解，求问大佬。
 | 1 iBugOne 2021-11-04 14:45:04 +08:00 都排好序了还不直接扫描 用归并排序中「归并一轮」这个操作的思路，你马上就知道第一个 list 里哪些数是夹在第二个 list 哪些数中间了 |
 | 2 zidian9 2021-11-04 14:57:11 +08:00 从前往后扫描，复杂度 O(m+n) |
 | 3 JKeita 2021-11-04 15:00:03 +08:00 双指针遍历不就行了？ |
| 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++ |
 | 5 NVDA 2021-11-04 15:18:22 +08:00 第二个列表如果排序了那就 binary search 找呗，最多是 mlogn |
 | 6 Jooooooooo 2021-11-04 15:20:17 +08:00 两个指针往前挪 |
 | 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 大小做选择 |
 | 8 byaiu 2021-11-05 08:44:54 +08:00 via iPhone list 不能随机存取吧…… |
Select Language