Extension problem of finding intersection of two sorted array# JobHunting - 待字闺中
f*4
1 楼
以后谁眼尖，第二楼就喊暗号，象土豆，神马都行。
版主就统一暗号吧
版主就统一暗号吧
b*8
2 楼
这是道老题。通常的方法是用两个pointers 从头到尾过两个arrays。复杂度是O(n).
但是如果一个array要比另一个大很多，则我们要Binary Search.复杂度是O(nlgm)。
扩展题是，在下面的情况下，how to optimize the search process (we may need to
switch between O(n) and O(nlgm) methods),
case 1:
v1: 1, 100, ......, 200,300,......,400
v2: 1,......, 100, 200, ......,300,400
case 2:
v1: 1,3,4,7,......,1M+1
v2: 2,4,6,8,...... 1M
case 3:
v1: 1,300, 5000, 70000, ......,1M+1
v2: 2,400, 6000, 80000, ......, 1M
求告人指点。
但是如果一个array要比另一个大很多，则我们要Binary Search.复杂度是O(nlgm)。
扩展题是，在下面的情况下，how to optimize the search process (we may need to
switch between O(n) and O(nlgm) methods),
case 1:
v1: 1, 100, ......, 200,300,......,400
v2: 1,......, 100, 200, ......,300,400
case 2:
v1: 1,3,4,7,......,1M+1
v2: 2,4,6,8,...... 1M
case 3:
v1: 1,300, 5000, 70000, ......,1M+1
v2: 2,400, 6000, 80000, ......, 1M
求告人指点。
t*e
3 楼
直接写，这是抄袭。
补上link。让大家你清我楚。
【在 f*****4 的大作中提到】
: 以后谁眼尖，第二楼就喊暗号，象土豆，神马都行。
: 版主就统一暗号吧
补上link。让大家你清我楚。
【在 f*****4 的大作中提到】
: 以后谁眼尖，第二楼就喊暗号，象土豆，神马都行。
: 版主就统一暗号吧
g*k
4 楼
就像你说的，这个就是由size决定的。
to
【在 b*******8 的大作中提到】
: 这是道老题。通常的方法是用两个pointers 从头到尾过两个arrays。复杂度是O(n).
: 但是如果一个array要比另一个大很多，则我们要Binary Search.复杂度是O(nlgm)。
: 扩展题是，在下面的情况下，how to optimize the search process (we may need to
: switch between O(n) and O(nlgm) methods),
: case 1:
: v1: 1, 100, ......, 200,300,......,400
: v2: 1,......, 100, 200, ......,300,400
: case 2:
: v1: 1,3,4,7,......,1M+1
: v2: 2,4,6,8,...... 1M
to
【在 b*******8 的大作中提到】
: 这是道老题。通常的方法是用两个pointers 从头到尾过两个arrays。复杂度是O(n).
: 但是如果一个array要比另一个大很多，则我们要Binary Search.复杂度是O(nlgm)。
: 扩展题是，在下面的情况下，how to optimize the search process (we may need to
: switch between O(n) and O(nlgm) methods),
: case 1:
: v1: 1, 100, ......, 200,300,......,400
: v2: 1,......, 100, 200, ......,300,400
: case 2:
: v1: 1,3,4,7,......,1M+1
: v2: 2,4,6,8,...... 1M
m*s
5 楼
老大爷来了。
行吗？
【在 f*****4 的大作中提到】
: 以后谁眼尖，第二楼就喊暗号，象土豆，神马都行。
: 版主就统一暗号吧
行吗？
【在 f*****4 的大作中提到】
: 以后谁眼尖，第二楼就喊暗号，象土豆，神马都行。
: 版主就统一暗号吧
b*8
6 楼
但是在给出的三个cases里面，他们的size都差不多。所以一般用O(n)的方法。扩展题
的意思能不能通过某种优化，有比O(n)更好的方法。
的意思能不能通过某种优化，有比O(n)更好的方法。
M*n
7 楼
坑和抄袭的确很讨厌,对付这类ID,最好的办法是常年置顶他们的帖子,羞死他们。我们
以前学校期中期末考舞弊被抓,名字都会在操场边上的报栏通告,威震效果很好。
以前学校期中期末考舞弊被抓,名字都会在操场边上的报栏通告,威震效果很好。
b*8
8 楼
有高人指点怎么优化1楼的三个cases吗？特别是case 2 and case 3?
f*4
9 楼
上link有点难，因为僵士们copy 和 paste的时侯图片没有，看着版面不一样。
我都是凭直觉。贴子格式有点怪的，称量方式不像是米国的，肯定是抄来的。
【在 t*****e 的大作中提到】
: 直接写，这是抄袭。
: 补上link。让大家你清我楚。
t*e
10 楼
那也没关系，把你的想法写出来，也许会有能人去查出来。
不过，如果，是猜的，就写猜的，有确定结果的话，请贴link
【在 f*****4 的大作中提到】
:
: 上link有点难，因为僵士们copy 和 paste的时侯图片没有，看着版面不一样。
: 我都是凭直觉。贴子格式有点怪的，称量方式不像是米国的，肯定是抄来的。
不过，如果，是猜的，就写猜的，有确定结果的话，请贴link
【在 f*****4 的大作中提到】
:
: 上link有点难，因为僵士们copy 和 paste的时侯图片没有，看着版面不一样。
: 我都是凭直觉。贴子格式有点怪的，称量方式不像是米国的，肯定是抄来的。
r*m
11 楼
你真逗。
用中国称量方式就是抄来的？
【在 f*****4 的大作中提到】
:
: 上link有点难，因为僵士们copy 和 paste的时侯图片没有，看着版面不一样。
: 我都是凭直觉。贴子格式有点怪的，称量方式不像是米国的，肯定是抄来的。
用中国称量方式就是抄来的？
【在 f*****4 的大作中提到】
:
: 上link有点难，因为僵士们copy 和 paste的时侯图片没有，看着版面不一样。
: 我都是凭直觉。贴子格式有点怪的，称量方式不像是米国的，肯定是抄来的。
r*m
12 楼
大部分同意版主的！
抄袭啥的太讨厌了，不过为了错杀好人，最好上link
【在 t*****e 的大作中提到】
: 那也没关系，把你的想法写出来，也许会有能人去查出来。
: 不过，如果，是猜的，就写猜的，有确定结果的话，请贴link
抄袭啥的太讨厌了，不过为了错杀好人，最好上link
【在 t*****e 的大作中提到】
: 那也没关系，把你的想法写出来，也许会有能人去查出来。
: 不过，如果，是猜的，就写猜的，有确定结果的话，请贴link
相关阅读
哪些IT公司有统计职位啊？那个skiplist的题谁来给谢谢question about official marriage certificate translation工作3个月的经历写在简历上么大头好像要闪人，要不要跟 (转载)真心请教A和M等公司可以申请多个职位吗？semiconductor process engineer 的statistical analysis要求是指什么？问个工资结构问题呢？求助： Amazon offer 只给10天的考虑时间，合理吗？如何handle?纽约州政府医院，招聘精神科医生psychiatrist请教 permute vector of vectors 如何实现，谢谢大家关于公司的活儿外包的问题有没有毕业几个月都没找到工作的码工Internal Refer avaiable简单说说两个L大家会在简历上直接说需要Sponsorship吗?Job title changeFrom Waiting list to 2nd Onsite after one month,求bless工资是manager还是HR定的