数组的公共数集
最原始的版本：给两个排序的，没有重复数字的数组，找他们的公共数集 (intersection)
Example:
array1 = [1,2,4,6,8] size m. From 1point 3acres bbs
array2 = [3,4,8] size n
return [4, 8]
解法1: time o(n), space o(n) 直接用set, 然后 返回 set(array1).union(array2)
解法2: time o(nlogn), space o(1) assume n < m, for i in array2, binary search i on array1
解法3: 双指针: merge sort: o(m+n)
follwo up1 :这个电面里没问，不过常考： 如果数字有重复怎么办， 其实解法3依旧使用，只不过要implement对
follwo up 2: 这里只有两个array, 如果有 M个array， 每个array平均N个数字， 现在要求M个array之间的两两之间的公共数集，也就是说原题这样的query要进行M^2次， 在什么情景下有什么样的优化 ？
> 说实话这里我愣了一下，没想出来什么情景，后来考官问，如果M >> N 呢？这里是个很重要的提示，这意味着这M^2个query里很多的答案都是0！然后我就马上想到了倒排索引，得到确认果然这是考官想要的(国人就是好说话，哈哈), 然后implement一下
这里要引入一个新的估计量: 假设每个数字出现的数组个数平均为L个, 则 L <= M (因为M >> N)举个例子
array1 = [1,2]
array2 = [1]
array3 = [2]
array4 = [1]. check 1point3acres for more.
...
array99 = [1]
array100 = [2]
(1) 搞一个map,就是倒排索引了： 以数字为key, value是一个list, list里面的内容是这个数字所在的数组，
比如上面的例子， 1:{array1, array2, array4, ...array99}, 2:{array1, array 2, array3...array100}， time: o(M*N) space (M*N)
(2) 然后再建一个map, key是array对子， value是公共数集，这个map的建立方法是遍历倒排索引，对每个key所在的list，两两枚举成array 对子， 这样的array{i}_{j}有M^2个
例子: 利用 (1) 中的1:{array1, array2, array4, ...array99},
对array1_2 所在entry append1,对array1_4 所在entry append1, 对array1_99 所在entry append1...
最后这样的array{i}_{j}有M^2个，但是事实上这个操作只进行了L^2*N次
复杂度: o(L^2 * N), space o(M^2*N)
然后比较一下复杂度
如果按原来的解法3， 复杂度为 O(M^2 * 2N)
如果按倒排索引，复杂度为 O(L^2*N)
可以看到哪怕是L=M，依旧是倒排索引占优， 减少一般时间，如果L < M 越小，优势越大，事实上L << M
https://www.1point3acres.com/bbs ... read&tid=499647
最原始的版本：给两个排序的，没有重复数字的数组，找他们的公共数集 (intersection)
Example:
array1 = [1,2,4,6,8] size m. From 1point 3acres bbs
array2 = [3,4,8] size n
return [4, 8]
解法1: time o(n), space o(n) 直接用set, 然后 返回 set(array1).union(array2)
解法2: time o(nlogn), space o(1) assume n < m, for i in array2, binary search i on array1
解法3: 双指针: merge sort: o(m+n)
follwo up1 :这个电面里没问，不过常考： 如果数字有重复怎么办， 其实解法3依旧使用，只不过要implement对
follwo up 2: 这里只有两个array, 如果有 M个array， 每个array平均N个数字， 现在要求M个array之间的两两之间的公共数集，也就是说原题这样的query要进行M^2次， 在什么情景下有什么样的优化 ？
> 说实话这里我愣了一下，没想出来什么情景，后来考官问，如果M >> N 呢？这里是个很重要的提示，这意味着这M^2个query里很多的答案都是0！然后我就马上想到了倒排索引，得到确认果然这是考官想要的(国人就是好说话，哈哈), 然后implement一下
这里要引入一个新的估计量: 假设每个数字出现的数组个数平均为L个, 则 L <= M (因为M >> N)举个例子
array1 = [1,2]
array2 = [1]
array3 = [2]
array4 = [1]. check 1point3acres for more.
...
array99 = [1]
array100 = [2]
(1) 搞一个map,就是倒排索引了： 以数字为key, value是一个list, list里面的内容是这个数字所在的数组，
比如上面的例子， 1:{array1, array2, array4, ...array99}, 2:{array1, array 2, array3...array100}， time: o(M*N) space (M*N)
(2) 然后再建一个map, key是array对子， value是公共数集，这个map的建立方法是遍历倒排索引，对每个key所在的list，两两枚举成array 对子， 这样的array{i}_{j}有M^2个
例子: 利用 (1) 中的1:{array1, array2, array4, ...array99},
对array1_2 所在entry append1,对array1_4 所在entry append1, 对array1_99 所在entry append1...
最后这样的array{i}_{j}有M^2个，但是事实上这个操作只进行了L^2*N次
复杂度: o(L^2 * N), space o(M^2*N)
然后比较一下复杂度
如果按原来的解法3， 复杂度为 O(M^2 * 2N)
如果按倒排索引，复杂度为 O(L^2*N)
可以看到哪怕是L=M，依旧是倒排索引占优， 减少一般时间，如果L < M 越小，优势越大，事实上L << M
https://www.1point3acres.com/bbs ... read&tid=499647
