帮忙看下一个非leetcode的经典题: k sorted array的所有公共元素

k个sorted array, 求所有array的公共元素
最优解能达到多少？ 先看下我的

1.   private static int intersect(int[] a, int[] b, int alen) {
   
2.         int commonCnt = 0, bIndex = 0;
   
3. 
   
4.         for (int aIndex = 0; aIndex < alen; ++aIndex) {
   
5.             while (bIndex < b.length && a[aIndex] > b[bIndex])
   
6.                 ++bIndex;
   
7. 
   
8.             if (bIndex == b.length)
   
9.                 break;
   
10. 
    
11.             if (a[aIndex] == b[bIndex]) {
    
12.                 a[commonCnt] = a[aIndex];
    
13.                 ++commonCnt;
    
14.                 ++bIndex;
    
15.             }
    
16.         }
    
17. 
    
18.         return commonCnt;
    
19.     }
    
20. 
    
21.     private static int intersectArrays(int[][] arrays) {
    
22.         int len = arrays[0].length;
    
23. 
    
24.         for (int i = 1; i < arrays.length; ++i) {
    
25.             len = intersect(arrays[0], arrays[i], len);
    
26.         }
    
27.         
    
28.         return len;
    
29.     }
    
30. 
    
31.     public static void main (String[] args) throws Exception
    
32.     {
    
33.         int[][] arr = {{1,2,3,3,4},{2,3,3,5},{1,2,3,3,5,6,7},{1,2,3,3,6,7,8,9}};
    
34.         int len = intersectArrays(arr);
    
35.         for (int i = 0; i < len; ++i)
    
36.             System.out.print(arr[0][i] + " ");
    
37.     }

复制代码

用一个globalmax记录candidate，记录每个subarray的index，如果小于globalmax就++，等于就去下一个subarray  counter++，大于就更新globalmax 重置counter，直到大家都找到了globalmax

时间上也是kn，空间上只有k

我觉得最好的办法应该是不用Heap 也不用Counter. 用Counter() 虽然是O(nk), 但是需要多遍处理。 第一遍是得到Counter(), 第二遍是对于一个Array中每个key在另一个的counter中是否出现。
如果用类似于 K merge sort的处理方式， 用一个K dimension array用来维护当前遍历到的每一个array的下标。 每次从第0个array中取出一个元素， 对于其他的数组，判断当前值是否等于该元素。 如果比这个值小，就移动下标，直到和当前值相等或者比当前值大，或者到当前Array的结束。 如果和当前值相等，那么下标需要继续后移一下。 然后用同样方法处理下一个数组。如果所有数组元素都可以找到相应值，那么说明其为公共元素，加入结果集合。 否则， 提前结束当前循环，考虑第0个Array的下一个元素。  这样一遍扫描即可找到答案

lkean9 发表于 2021-7-20 04:23
我看到这个是前几个月谷歌的一个phone screen，然后考虑了一下，感觉最简单的一种做法就是用python的collec ...

这题要追求效率，没必要用Heap额，效率反而是下降的，直接无脑线性hashmap映射不就完事了么，假设最长数组的长度为n，那么最后的时间复杂度就是O(kn)。
但如果使用heap则会变成O(Nlogk)，而这里的N是总元素数目，在效率是是不如O(kn)的额。


而且可以简单证明一下时间复杂度不太可能低于O(kn)，或者说这道题的时间复杂度是的Ω(kn)。我们可以先把k sorted array退化成 2 sorted array，那么现在时间复杂度是O( 2 n ) = O( n )，也就是说如果我们能把退化后的情况优化成小于O(n)，那么原题目自然就能进行优化。

但是如果能优化小于O(n)，意味着什么呢？意味着我们不需要查看每一个元素一次，但是如果在最坏情况下，公共元素刚好等于n，那么这种情况我们必须查看和报告n个元素，所以再怎么优化，也不能由于O(n)，那么比2个数组更难得k个数组，自然也不能优化小于O(kn)

请问每个sorted areay中会有重复元素吗

lkean9 发表于 2021-7-19 08:37
请问每个sorted areay中会有重复元素吗

有的 8个字才能提交

我看到这个是前几个月谷歌的一个phone screen，然后考虑了一下，感觉最简单的一种做法就是用python的collections.Counter把每个sub-array都转化成counter，然后一个一个校核就可以了。这样时间是O(nk), 空间是O(n), n是subarray平均长度（请注意这里的n的定义），k是subarray的个数。

还有一种用heap做的，时间为O(Nlogk)，N是total numbers of sorted arrays（元素总数，与之前n的定义不同），k依旧是subarray的个数，具体思路有点儿接近于Leetcode 23(hard) mege k-sorted lists，是每个loop都将每个subarray的当前最小元素push进heap，同时还需要记录subarray的index，然后当heap中的同一个num出现次数等于k时，这个num就是一个intersection value。如果num次数不等于k，就将其pop出去，重新从sorted arrays[index]的那个subarray push接下来的最小元素。但是具体实现是真的麻烦，因为要判断一个元素出现的次数，比LC23有更多的判断条件，所以感觉下面的做法更直观一些。。。顺便求点儿大米 : )

1. import collections
   
2. from typing import List
   
3. 
   
4. 
   
5. class Solution:
   
6.     """
   
7.     convert each sorted array to the counter, then find intersection one by one
   
8.     Time O(kn), Space O(n) where:
   
9.     k is number of sorted arrays
   
10.     n is the average length of the sorted array
    
11.     """
    
12. 
    
13.     def intersectArrays(self, arrays: List[List[int]]) -> List[int]:
    
14.         k = len(arrays)
    
15.         if k == 0:
    
16.             return []  # edge case
    
17.         if k == 1:
    
18.             return arrays[0]  # edge case
    
19.         for i in range(k):
    
20.             if len(arrays[i]) == 0:
    
21.                 return []  # edge case
    
22. 
    
23.         interSect = {}
    
24.         counter1 = collections.Counter(arrays[0])
    
25.         counter2 = collections.Counter(arrays[1])
    
26. 
    
27.         for num, occurrence in counter2.items():
    
28.             if num in counter1:
    
29.                 interSect[num] = min(counter1[num], occurrence)
    
30. 
    
31.         for i in range(2, k):
    
32.             counter2 = collections.Counter(arrays[i])
    
33. 
    
34.             for num, occurrence in counter2.items():
    
35.                 if num in interSect:
    
36.                     interSect[num] = min(counter1[num], occurrence)
    
37. 
    
38.         res = []
    
39.         for num, occurrence in interSect.items():
    
40.             res.extend([num] * occurrence)
    
41. 
    
42.         return res
    
43. 
    
44. 
    
45. s = Solution()
    
46. arrays = [[0, 1, 2, 3, 3, 4], [2, 3, 3, 5], [1, 2, 3, 3, 5, 6, 7], [3, 3, 6, 7, 8, 9], []]
    
47. print(s.intersectArrays(arrays))

复制代码

[/i][/i]


补充内容 (2021-07-20 05:17 +08:00):
不懂为啥在电脑上显示的代码是好的，但在手机上看就成了文本显示了。。。

顺便一提，稍微思考一下merge k sorted array和 intersection of k sorted array的算法上的区别，其实还是很明晰的。

为啥intersection用直观的O(nk)就可以呢，n为sub-array的平均/最大长度？是因为intersection list中可能的最大元素个数就是n，不可能超过n，每次循环intersection list长度可能越来越小，所以就是O(n + n + n+...+n) = O(kn)。

再来看merge，如果用上述方法，先merge 两个list，再merge第三个，以此类推。merge list就会越来越大，最后在k次循环下，就变成了O(n*(2+3+ ... +k)) = O(Nk), N为所有元素个数，所以用heap可以稍微优化时间了

感觉这样的解释用来应付一个phone screen应该是足够了

这个用heap呀

thrillerの空 发表于 2021-07-19 19:43:37
这题要追求效率，没必要用Heap额，效率反而是下降的，直接无脑线性hashmap映射不就完事了么，假设最长数组的长度为n，那么最后的时间复杂度就是O(kn)。
但如果使用heap则会变成O(Nlog

是的，完全同意。所以我也想到，如果是merge k sorted arrays就用heap来做（leetcode 23)，时间复杂度O(Nlogk)，N是所有元素的个数。如果是intersection of k arrays，不管有没有sorted，其实就用最简单的算法O(nk)完事儿了

lkean9 发表于 2021-7-20 04:23
我看到这个是前几个月谷歌的一个phone screen，然后考虑了一下，感觉最简单的一种做法就是用python的collec ...

第一种方法是不是不需要 sorted