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
Mirage09 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 不能随机存取吧……
|