寻找两个数组中是否有公共元素的递归算法

output.txt

------N=10---------
递归算法实际执行次数:	29
O(N^log2(3))估计次数:	38
O(M+N)算法最坏次数为:	20
------N=20---------
递归算法实际执行次数:	86
O(N^log2(3))估计次数:	115
O(M+N)算法最坏次数为:	40
------N=40---------
递归算法实际执行次数:	261
O(N^log2(3))估计次数:	346
O(M+N)算法最坏次数为:	80
------N=80---------
递归算法实际执行次数:	780
O(N^log2(3))估计次数:	1038
O(M+N)算法最坏次数为:	160
------N=160---------
递归算法实际执行次数:	2345
O(N^log2(3))估计次数:	3114
O(M+N)算法最坏次数为:	320
------N=320---------
递归算法实际执行次数:	7028
O(N^log2(3))估计次数:	9344
O(M+N)算法最坏次数为:	640
------N=640---------
递归算法实际执行次数:	21093
O(N^log2(3))估计次数:	28034
O(M+N)算法最坏次数为:	1280
------N=1280---------
递归算法实际执行次数:	63264
O(N^log2(3))估计次数:	84102
O(M+N)算法最坏次数为:	2560
------N=2560---------
递归算法实际执行次数:	189809
O(N^log2(3))估计次数:	252308
O(M+N)算法最坏次数为:	5120
------N=5120---------
递归算法实际执行次数:	569396
O(N^log2(3))估计次数:	756926
O(M+N)算法最坏次数为:	10240
------N=10240---------
递归算法实际执行次数:	1708221
O(N^log2(3))估计次数:	2270779
O(M+N)算法最坏次数为:	20480
------N=20480---------
递归算法实际执行次数:	5124600
O(N^log2(3))估计次数:	6812339
O(M+N)算法最坏次数为:	40960
------N=40960---------
递归算法实际执行次数:	15373865
O(N^log2(3))估计次数:	20437019
O(M+N)算法最坏次数为:	81920
------N=81920---------
递归算法实际执行次数:	46121468
O(N^log2(3))估计次数:	61311058
O(M+N)算法最坏次数为:	163840
------N=163840---------
递归算法实际执行次数:	138364533
O(N^log2(3))估计次数:	183933174
O(M+N)算法最坏次数为:	327680
------N=327680---------
递归算法实际执行次数:	415093344
O(N^log2(3))估计次数:	551799524
O(M+N)算法最坏次数为:	655360

Solution.java

// https://leetcode.com/problems/intersection-of-two-arrays/

class Solution {
    public static List<Integer> common = new ArrayList<>();
    public static boolean find(int[] arr1, int i1, int j1, int[] arr2, int i2, int j2) {
        if (i1 > j1 || i2 > j2) return false;
        int mid1 = (i1 + j1) / 2;
        int mid2 = (i2 + j2) / 2;
        if (arr1[mid1] == arr2[mid2]) {
            common.add(arr1[mid1]);
            return true;
        } else if (arr1[mid1] < arr2[mid2]) {
            return find(arr1, i1, mid1, arr2, i2, mid2 - 1) || find(arr1, mid1 + 1, j1, arr2, mid2, j2) || find(arr1, mid1 + 1, j1, arr2, i2, mid2 - 1);
        } else {
            return find(arr1, i1, mid1 - 1, arr2, i2, mid2) || find(arr1, mid1, j1, arr2, mid2 + 1, j2) || find(arr1, i1, mid1 - 1, arr2, mid2, j2);
        }
    }
    
    public static boolean find(int[] arr1, int[] arr2) {
        return find(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1);
    }

    public static int[] removeElement(int[] arr, int target) {
        return IntStream.of(arr).filter(item -> item != target).toArray();
    }
    
    public static int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> res = new ArrayList<>();
        nums1 = IntStream.of(nums1).sorted().distinct().toArray();
        nums2 = IntStream.of(nums2).sorted().distinct().toArray();
        while (true) {
            common = new ArrayList<>();
            boolean flag = find(nums1, nums2);
            if (!flag) {
                break;
            } else {
                int commonInt = common.get(0);
                nums1 = removeElement(nums1,commonInt);
                nums2 = removeElement(nums2,commonInt);
                res.add(commonInt);
            }
        }
        return res.stream().mapToInt(i->i).toArray();
    }

}

TwoArraySearchCommon.java

public class TwoArraySearchCommon {

    public static int N = 0;

    public static boolean find(int[] arr1, int i1, int j1, int[] arr2, int i2, int j2) {

        if (i1 > j1 || i2 > j2) return false;
        int mid1 = (i1 + j1) / 2;
        int mid2 = (i2 + j2) / 2;
        N++;
        if (arr1[mid1] == arr2[mid2]) {
            System.out.println(mid1);
            System.out.println(mid2);
            return true;
        } else if (arr1[mid1] < arr2[mid2]) {
            return find(arr1, i1, mid1, arr2, i2, mid2 - 1) || find(arr1, mid1 + 1, j1, arr2, mid2, j2) || find(arr1, mid1 + 1, j1, arr2, i2, mid2 - 1);
        } else {
            return find(arr1, i1, mid1 - 1, arr2, i2, mid2) || find(arr1, mid1, j1, arr2, mid2 + 1, j2) || find(arr1, i1, mid1 - 1, arr2, mid2, j2);
        }
    }


    public static void main(String[] args) {
        for (int len = 10; len < 999999999; len *= 2) {
            int[] a = new int[len];
            int[] b = new int[len];
            for (int i = 0; i < len; i++) {
                a[i] = i;
                b[i] = len + i;
            }
            System.out.println("------N=" + len + "---------");
            N = 0;find(a, 0, a.length - 1, b, 0, b.length - 1);
            System.out.println("递归算法实际执行次数:\t" + N);
            System.out.println("O(N^log2(3))估计次数:\t" + (int) Math.pow(len, 1.5849625007211563));
            System.out.println("O(M+N)算法最坏次数为:\t" + 2 * len);
        }
    }
}