查找这是常见的两个数组的最大元素？ [英] 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?

我想整理的两个阵列（N日志N），然后执行从一个排序的数组中每个元素的二进制搜索的另一个数组（从较大的开始），直到找到匹配的。

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.

例如：

a = [1,2,5,4,3]
b = [9,8,3]

Maximum common element in these array is 3

我们可以做多于n日志ñ更好？

Can we do better than n log n?

推荐答案

通过一些额外的空间，你可以散列在1阵列，然后做一个包含返回true最大价值的其它阵列跟踪中的每个元素。会为O（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).

这篇关于查找这是常见的两个数组的最大元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！