discussion7

CS61B

第一题基本没什么问题：

第二题

第二题的正确答案是：

发现worst case的runtime是O（M+N），不大明白为什么，群里有人如此解答：

首先，for循环中int j = 0 初始化在外面，意味着当i = N, j从0逐渐增加到M后，i变为N - 1，但j不会再初始化回0，而是从j = M开始；
当发现j = M + 1时，就不满足条件，这类循环了 m + 1次（j = 0 to j = m);之后还有 N - 1 次校验（j < = m) (n = n - 1到 n = 1 各一次共 N- 1次）；

第二题还有两个问，分别问了mystery()这个方法是干什么的，以及有没有更好的方法来执行，更优的runtime：

参考答案：

第三题，最简单的twoSum：

有更快的方法吗？查了下网上，这比通常的twoSum还要简单：

参考答案的方法更简易：

最后一题，基础面试题，但这里标记是for experts：

我给的解法：

发现自己完全是想模仿之前看到的那个O（M+N），然而并不懂是否可以依葫芦画瓢……

参考答案用到了HashSet, 我还没学过，真的该自问是否能做for experts的题目了，不过明天又多了可以学习的新东西：

这里主要运用到HashSet不能有重复的元素这一特点

自己动手写一遍：

最后一道题我要求自己独立做好，因为瞟了一眼答案，发现也是用的HashSet:

发现跟答案思路比较像，只是用来判断是不是duplicate的方法不一样。我是用的HashSet里的boolean add(Object o)来判断，答案是用boolean contains(Object o), 顺便看一下HashSet的主要方法：

但测试代码的时候发现我好像错了：

我错在：

• 空数组不等于null
• 我用add来判断HashSet是否包含某个元素很容易造成干扰，比如A本来是空数组，用这个方法来判断是否包含某个元素时，就已经在往A里添加元素了；

如果“空数组”是指“长度为0的数组”，那么一个空数组就和一个长度为0的数组没有区别。
如果“空数组”是指“引用为null的数组变量”，那么二者有区别：一个空数组的引用是null；一个长度为0的数组的引用不是null，而是一个长度为0的数组。

useful:
java中一个空数组与一个长度为0的数组有什么区别呀？

所以改成正确的答案：

但问Runtime的时候，还不太清楚为什么是Θ（M+N）：
我暂时理解为要遍历两个数组A和B，分别为size M,N,所以不管worst case or best case都需要（M + N)

参考：
Java HashSet class
HashSet Class in Java with example