如何计算两个有序整型数组的交集

数据结构与算法

问题描述：假设两个含有n个元素的有序（非降序）整型数组a和b，其中a={0,1,2,3,4}.b={1,3,5,7,9}.那么他们的交集为{1，3}

1.长度差不多的情况下

1. 二路归并法
2. 放入哈希表
3. 散列

哈希表不是很正确，。因为，非降序应该是代表着可以相等的情况。
散列，。，。不会呀

public class Solution {
    public ArrayList<Integer> mix(int[] a, int[] b) {
        if(a==null|||b==null){
            return null;
        }
        int len = a.length + b.length;
        ArrayList<Integer> result = new ArrayList<>();
        int i = 0;
        int j = 0;
        int counter = 0;
        while (counter < len) {
            if (i >= a.length) {
                break;
            } else if (j >= b.length) {
                break;
            } else if (a[i] == b[j]) {
                counter++;
                result.add(a[i]);
                i++;
                j++;
            } else if (a[i] < b[j]) {
                i++;
            } else if (a[i] > b[j]) {
                j++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] a = {1, 2, 3};
        int[] b = {1, 3, 4};
        System.out.println(solution.mix(a, b));
    }
}

2.长度悬殊较大

遍历短数组，在长数组中进行二分搜索

public class Solution {
    public ArrayList<Integer> mix(int[] a, int[] b) {
        if (a == null || b == null) {
            return null;
        }
        ArrayList<Integer> result = new ArrayList<>();
        int lenA = a.length;
        int lenB = b.length;
        int[] temp = null;
        if (lenA < lenB) {
            temp = a;
            a = b;
            b = temp;
        }
        for (int i = 0; i < lenB; i++) {
            boolean find = binarySearch(a, 0, a.length - 1, b[i], false);
            if (find) {
                result.add(b[i]);
            }
        }
        return result;
    }
    public boolean binarySearch(int[] nums, int left, int right, int target, boolean find) {
        if (left > right) {
            return find;
        }
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            find = true;
            return find;
        } else if (nums[mid] > target) {
            return binarySearch(nums, left, mid - 1, target, find);
        } else {
            return binarySearch(nums, mid + 1, right, target, find);
        }
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25};
        int[] b = {1, 3, 4, 25};
        System.out.println(solution.mix(a, b));
    }
}

优化的二分,返回索引

public class Solution {
    public ArrayList<Integer> mix(int[] a, int[] b) {
        if (a == null || b == null) {
            return null;
        }
        ArrayList<Integer> result = new ArrayList<>();
        int lenA = a.length;
        int lenB = b.length;
        int[] temp = null;
        if (lenA < lenB) {
            temp = a;
            a = b;
            b = temp;
        }
        int left = 0;
        int right = lenA - 1;
        int find = -1;
        for (int i = 0; i < lenB; i++) {
            find = binarySearch(a, left, right, b[i], Integer.MAX_VALUE);
            if (find != Integer.MAX_VALUE) {
                result.add(a[find]);
                left = find;
            }
        }
        return result;
    }
    public int binarySearch(int[] nums, int left, int right, int target, int find) {
        if (left > right) {
            return find;
        }
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            find = mid;
            return find;
        } else if (nums[mid] > target) {
            return binarySearch(nums, left, mid - 1, target, find);
        } else {
            return binarySearch(nums, mid + 1, right, target, find);
        }
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25};
        int[] b = {1, 3, 4, 25};
        System.out.println(solution.mix(a, b));
    }
}