首页 > 代码库 > 找出两个整型数组中的公共元素的最大值
找出两个整型数组中的公共元素的最大值
一，问题描述
给定两个整型数组，找出这两个数组中的最大的公共元素。注意条件：①公共元素 ②最大的公共元素
比如：arr1={8,2,9,6,18,7,25,28} arr2={6,39,4,9,25,18,36,12}.假设 arr1 的长度为M，arr2的长度为N
这两个数组的最大公共元素是：25
二，思路
①对 arr1 中的每个元素arr1[i]，去 arr2 查找是否也存在 该元素，若存在则标记起来，因为它虽然是公共的，但不一定是最大的。
直到扫描完arr1中的所有元素，这种方式的时间复杂度为O(MN)，空间复杂度为O(1)
②先对数组 arr1 排序，再对 arr2 排序。再定义两个指针 i, j 分别指向 arr1 和 arr2 中的最后一个元素。比较这两个数组中的最后一个元素，若相等则找到了所求的元素；若不相等，将指向较大的那个元素的指针 前移一位(减1)。
排序的时间复杂度为O(MlogM + NlogN)，最坏情况下指针遍历的时间复杂度为O(M+N)，故总的时间复杂度为O(MlogM+NlogN)
③采用 堆 来实现
对两个数组分别构造两个大顶堆，若堆顶元素相同，则堆顶元素就是公共最大的元素。否则，删除较大的那个堆顶元素，进行堆调整，继续比较。
数组1建堆的时间复杂度为O(M)，数组2建堆的时间复杂度为O(N)
一般对于删除堆顶元素，进行堆调整而言，平均情况下的时间复杂度为O(1)。故平均情况下，时间复杂度应该要比 方法② 中的小。
另外，可以直接在原数组上进行建堆操作，此时空间复杂度为O(1)
三，方法③代码实现
核心代码如下：
1 int len_1 = arr1.length - 1; 2 int len_2 = arr2.length - 1; 3 while(len_1 >= 0 && len_2 >=0) 4 { 5 int max1 = arr1[0];//获取大顶堆的根元素,即数组中的最大值 6 int max2 = arr2[0]; 7 8 if(max1 > max2)//如果arr1的堆顶元素要大,则删除arr1的堆顶元素 9 {10 swap(arr1, 0, len_1);//delete arr1‘s root11 percDown(arr1, 0, len_1);//进行堆调整, 删除了最后一个元素,刚好堆调整的元素个数为 len_112 len_1--;13 }14 else if( max1 < max2)//如果arr2的堆顶元素要大,则删除arr2的堆顶元素15 {16 swap(arr2, 0, len_2);17 percDown(arr2, 0, len_2);18 len_2--;19 }20 else//arr1的堆顶元素与 arr2的堆顶元素相等了.21 return max1;22 }
当建立了两个大顶堆后，比较这两个大顶堆的堆顶元素，谁大，则删除谁。当然，删除了堆顶元素之后，需要进行堆调整以保证堆的性质。
第10行的swap方法就表示 删除堆顶元素，第11行的percDown方法表示 堆调整。
不断地删除堆顶元素，直到：①某个堆中的元素都被删除了（此时 while循环条件不成立了）这表明：两个数组中没有公共元素。
②若两个堆的堆顶元素相同了(第20-21行)，则表明找到了最大公共元素。
算法的正确性说明：因为使用的是大顶堆。堆顶元素一定是当前数组中最大的元素，而通过比较两个堆顶元素，若不相等，则删除较大的堆顶元素，这样总能保证：优先找到两个堆中目前相同且最大的元素。
完整代码实现：
//给定两个整形数组,寻找这两个数组的公有的且最大的元素public class MaxCommonEle { public static int findCommMax(int[] arr1, int[] arr2) { if(arr1 == null || arr2 == null) throw new NullPointerException(); if(arr1.length == 0 || arr2.length == 0) throw new IllegalArgumentException(); //build heap--大顶堆 , time complex: O(M) for(int i = arr1.length / 2 -1; i >= 0; i--) percDown(arr1, i, arr1.length); //build heap, O(N) for(int i = arr2.length / 2 - 1; i >= 0; i--) percDown(arr2, i, arr2.length); int len_1 = arr1.length - 1; int len_2 = arr2.length - 1; while(len_1 >= 0 && len_2 >=0) { int max1 = arr1[0];//获取大顶堆的根元素,即数组中的最大值 int max2 = arr2[0]; if(max1 > max2)//如果arr1的堆顶元素要大,则删除arr1的堆顶元素 { swap(arr1, 0, len_1);//delete arr1‘s root percDown(arr1, 0, len_1);//进行堆调整, 删除了最后一个元素,刚好堆调整的元素个数为 len_1 len_1--; } else if( max1 < max2)//如果arr2的堆顶元素要大,则删除arr2的堆顶元素 { swap(arr2, 0, len_2); percDown(arr2, 0, len_2); len_2--; } else//arr1的堆顶元素与 arr2的堆顶元素相等了. return max1; } return -1;// -1 means there are no common element } private static void percDown(int[] arr, int i, int n) { int tmp; int child; // int k = leftChild(i); for(tmp = arr[i]; leftChild(i) < n; i = child) { child = leftChild(i); if(child != n-1 && arr[child] < arr[child+1]) child = child + 1; if(tmp < arr[child]) arr[i] = arr[child]; else break; } arr[i] = tmp; } private static int leftChild(int i){ return (i << 1 ) + 1; } private static void swap(int[] arr ,int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } //hapjin test public static void main(String[] args) { int[] arr1 = {8,2,9,6,18,7,25,28}; int[] arr2 = {6,39,4,9,25,18,36,12}; // int[] arr1 = {4,2,8};// int[] arr2 = {10,4,6};// int[] arr1 = {4,2,8};// int[] arr2 = {5,7,9}; int res = findCommMax(arr1, arr2); System.out.println(res); }}
四，参考资料
数据结构--堆的实现之深入分析
找出两个整型数组中的公共元素的最大值