出一道我发明的题，难度算简单吧。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

出一道我发明的题，难度算简单吧。

出一道我发明的题，难度算简单吧。# JobHunting - 待字闺中

P*e2018-02-07 08:02

1 楼

有两个有序的array of strings,
array1 = ["abc","def","ghi","jkl"]
array2 = ["abc","jkl"]
返回所有在array1但不在array2的单词： ["def","ghi"]
array1 = ["Zebra"]
array2 = ["Antelope","Bison","Cow"]
返回 ["Zebra"]
限制：不允许吧两个array加入两个hashmap或set然后比较两者差。

o*r2018-02-07 08:02

2 楼

Tries Tree? Node里面存一个指向下一层的Node数组，再存一个是否是一个结束。
--------------
我擦，没看到有序。。。。>.<

c*w2018-02-07 08:02

3 楼

真的简单。每个数组个一个指针扫。O(n m)搞定
// assume both input arrays are not null, but can be empty
i=0;
j=0;
output = [];
while(i < arrry1.length()) {
if (j >= array2.length() || array1[i] < array2[j]) {
output[] = array1[i];
i ;
}
else if (array1[i] == array2[j])
i ;
else // array1[i] > array2[j]
j ;
}
return output;

d*n2018-02-07 08:02

4 楼

楼主怕是没刷过题 lc里面trie只要做过这个题3分钟手写的水平吧

d*b2018-02-07 08:02

5 楼

一行搞定。。。。。
int main() {
std::vector v1 {"Zebra"};
std::vector v2 {"Antelope", "Bison", "Cow"};
std::vector diff;
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_
inserter(diff));
return 0;
}

d*b2018-02-07 08:02

6 楼

看来你的题是白刷了，还 Trie。
你咋不说 async + promise 再加一个分布式解法？

G*O2018-02-07 08:02

7 楼

两个指针扫一遍不就行了？ O( max (m, n))

s*u2018-02-07 08:02

8 楼

双指针，相等则记录，不相等挪更小的指针，因为有序。第二个指针到底后可以直接返
回。
lc这类变形题很多。

t*u2018-02-07 08:02

9 楼

有序，就做一步类似于merge sort里面的merge操作。

c*a2018-02-07 08:02

10 楼

典型的刷题刷傻了的例子。

【在 d*******n 的大作中提到】

: 楼主怕是没刷过题 lc里面trie只要做过这个题3分钟手写的水平吧

z*n2018-02-07 08:02

11 楼

等价
两个有序数组，
1 2 3 4 5
3 5 7
找difference
LC easy- 的题。

P*e2018-02-07 08:02

12 楼

你们都没考虑这两个词组里都可能出现重复的词。

b*62018-02-07 08:02

13 楼

保留或剔除重复结果太容易了
你要找的是在list1里出现但是不在list2里的，在list1, list2里各放一个指针ptr1,
ptr2，如果ptr1大于ptr2就增加ptr2

【在 P****e 的大作中提到】

: 你们都没考虑这两个词组里都可能出现重复的词。

P*e2018-02-07 08:02

14 楼

没那么简单。
s1= "abc def def def efg efg hij hij xyz"
s2 = "ab def def hij klm klm klm"
返回 abc, efg, xyz

z*n2018-02-07 08:02

15 楼

你有序的不是，那为啥去重很难？指针加一时看一下上一个单词和自己一样不一样就行
了。还有啥需要考虑的？

【在 P****e 的大作中提到】

: 没那么简单。
: s1= "abc def def def efg efg hij hij xyz"
: s2 = "ab def def hij klm klm klm"
: 返回 abc, efg, xyz

z*n2018-02-07 08:02

16 楼

你有序的不是，那为啥去重很难？指针加一时看一下上一个单词和自己一样不一样就行
了。还有啥需要考虑的？

【在 P****e 的大作中提到】

: 没那么简单。
: s1= "abc def def def efg efg hij hij xyz"
: s2 = "ab def def hij klm klm klm"
: 返回 abc, efg, xyz

f*r2018-02-07 08:02

17 楼

這有什麼難的，兩個同時掃，和merge sort差不多

【在 P****e 的大作中提到】

: 有两个有序的array of strings,
: array1 = ["abc","def","ghi","jkl"]
: array2 = ["abc","jkl"]
: 返回所有在array1但不在array2的单词： ["def","ghi"]
: array1 = ["Zebra"]
: array2 = ["Antelope","Bison","Cow"]
: 返回 ["Zebra"]
: 限制：不允许吧两个array加入两个hashmap或set然后比较两者差。