我今天在一次采访中被问到一个算法问题,我很想得到 SO 成员的意见。问题如下;
给定大小相同的 N 个数组,整数按升序排列,你将如何选择所有 N 个数组共有的数字。
起初,我的想法是从第一个数组开始迭代元素,一直到其他数组。但是,如果我是对的,那将导致 N 次幂 N 次迭代。因此,我想出了一个解决方案,通过将元素作为键并将值作为计数器来将计数添加到地图中。这样我相信时间复杂度只是N。以下是我的方法在Java中的实现
public static void main(String[] args) {
int[] arr1 = { 1, 4, 6, 8,11,15 };
int[] arr2 = { 3, 4, 6, 9, 10,16 };
int[] arr3 = { 1, 4, 6, 13,15,16 };
System.out.println(commonNumbers(arr1, arr2, arr3));
}
public static List<Integer> commonNumbers(int[] arr1, int[] arr2, int[] arr3) {
Map<Integer, Integer>countMap = new HashMap<Integer, Integer>();
for(int element:arr1)
{
countMap.put(element, 1);
}
for(int element:arr2)
{
if(countMap.containsKey(element))
{
countMap.put(element,countMap.get(element)+1);
}
}
for(int element:arr3)
{
if(countMap.containsKey(element))
{
countMap.put(element,countMap.get(element)+1);
}
}
List<Integer>toReturn = new LinkedList<Integer>();
for(int key:countMap.keySet())
{
int count = countMap.get(key);
if(count==3)toReturn.add(key);
}
return toReturn;
}
我只是为三个数组做了这个,看看它是如何工作的。问题谈论 N Arrays 虽然我认为这仍然存在。
我的问题是,考虑到时间复杂度,有没有更好的方法来解决这个问题?