问题描述:

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;
```

您可能感兴趣的文章：

- iphone - Icenium no provisioning profile found
- search - ElasticSearch and Python - Correct methodolgy
- oracle11g - Can not import a file created by data-pump when there are tables with partition by reference
- (JAVA) if statement
- java - Framework that uses DTOs or beans to create a databse
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**