当前位置: 动力学知识库 > 问答 > 编程问答 >

algorithm - Find the maximum element which is common in two arrays?

问题描述:

Given two arrays, how to find the maximum element which is common to both the arrays?

I was thinking of sorting both the arrays(n log n) and then perform the binary search of every element from one sorted array(starting from larger one) in another array until match is found.

eg:

a = [1,2,5,4,3]

b = [9,8,3]

Maximum common element in these array is 3

Can we do better than n log n?

网友答案:

With some extra space you could hash in 1 array, then do a contains on each element of the other array keeping track of the biggest value that returns true. Would be O(n).

网友答案:

You can but using O(N) space.
Just go through the first array and place all elements in a HashTable. This is O(N)
Then go through the second array keeping track of the current maximum and checking if the element is in the HashTable. This is also O(N) . So total runtime is O(N) and O(N) extra space for the HashTable

Example in Java:

public static int getMaxCommon(int[] a, int[] b){  
  Set<Integer> firstArray = new HashSet<Integer>(Arrays.asList(a));  
  int currentMax = Integer.MIN_VALUE;  
  for(Integer n:b){  
     if(firstArray.contains(n)){  
         if(currentMax < n){  
              currentMax = n  
         }
     }   
  }   
  return currentMax;  
}  
网友答案:

While it depends on the time complexities of the various operations in specific languages, how about creating sets from the arrays and finding the maximum value in the intersection of the two sets? Going by the time complexities for operations in Python, it'd be, on average, O(n) for the set assignments, O(n) for the intersections, and O(n) for finding the max value. So average case would be O(n).

However! Worst-case would be O(len(a) * len(b)) -> O(n^2), because of the worst-case time complexity of set intersections.

More info here, if you're interested: http://wiki.python.org/moin/TimeComplexity

网友答案:

If you already know the range of numbers that would be in your arrays, you could perform counting sort, and then perform the binary search like you wanted. This would yield O(n) runtime.

网友答案:

Pseudocode:

sort list1 in descending order
sort list2 in descending order
item *p1 = list1
item *p2 = list2
while ((*p1 != *p2) && (haven't hit the end of either list))
  if (*p1 > *p2)
    ++p1;
  else
    ++p2;
// here, either we have *p1 == *p2, or we hit the end of one of the lists
if (*p1 == *p2)
  return *p1;
return NOT_FOUND;
分享给朋友:
您可能感兴趣的文章:
随机阅读: