没有循环的整数数组交集递归

Question

在我最近的作业中，我应该使用递归和无循环找到两个整数数组之间的交集（可能也没有专门的方法，但它没有指定）。

输入数组

[1, 4, 4, 5, 8, 19, 23, 42, 73]
[1, 4, 5, 9, 17, 21, 42, 73]

预期输出（交集数组）

[1, 4, 4, 5, 42, 73]

到目前为止我得到的是：

public static int[] arrayIntersection(int[] a, int[] b) {
    int [] result = new int[0];
    //System.out.println("a.length: " + a.length + "\nb.length: " + b.length + "\n\n");
    if (a.length > 1) {
        int[] temp = arrayIntersection(shorten(a), b);
        result = append(result, temp);
    }
    if (b.length > 1) {
        int[] temp = arrayIntersection(a, shorten(b));
        result = append(result, temp);
    }
    if(a[a.length - 1] == b[b.length - 1]) result = append(result, a[a.length - 1]);
    return result;
}

public static int[] sortedArrayIntersection(int[] a, int[] b) {
    return new int[0]; // b)
}

public static int[] append(int[] a, int[]b) {
    int[] appended = a;
    if (b.length > 0) {
        appended = Arrays.copyOf(a, a.length + 1);
        appended[appended.length - 1] = b[b.length - 1];
        if (b.length > 1) appended = append(appended, shorten(b));
    }
    return appended;
}

public static int[] append(int[] a, int b) {
    int[] appended = a;
    appended = Arrays.copyOf(a, a.length + 1);
    appended[appended.length - 1] = b;
    return appended;
}

public static int[] shorten(int[] a) {
    return Arrays.copyOf(a, a.length-1);
}

但是这会多次检查相同的对，因此产生的输出太长了。

帮助我 Stack Overflow 你是我唯一的希望。

Answer 1

最简单的方法是首先找出哪个数组更长。

import java.util.Arrays;

public class Intersect {
    /**
     * Returns the intersection of two arrays.
     * 
     * @param arr1  First array.
     * @param arr2  Second array.
     * @return
     */
    public static int[] intersection(int[] arr1, int[] arr2) {
        if (arr1 == null || arr2 == null) {
            return null;
        } else if (arr1.length == 0 || arr2.length == 0) {
            return new int[0];
        } else if (arr1.length > arr2.length) {
            return intersection(arr1, arr2, new int[arr2.length], 0, 0, 0);
        } else {
            return intersection(arr2, arr1, new int[arr1.length], 0, 0, 0);
        }
    }

    /**
     * Internal recursive function to generate intersecting array.
     * 
     * @param arrL   Longer array.
     * @param arrS   Shorter array.
     * @param arrI   Intersection array.
     * @param stepL  Longer array step.
     * @param stepS  Shorter array step.
     * @param stepI  Intersection array step.
     * @return
     */
    private static int[] intersection(int[] arrL, int[] arrS, int[] arrI, int stepL, int stepS, int stepI) {
        if (stepL > arrS.length) {
            return Arrays.copyOf(arrI, stepI);
        }

        int valL = arrL[stepL], valS = arrS[stepS];

        if (valL == valS) {
            arrI[stepI++] = valL;
        }

        stepS++;

        if (stepS > arrS.length - 1) {
            stepS = 0;
            stepL++;
        }

        return intersection(arrL, arrS, arrI, stepL, stepS, stepI);
    }

    public static void main(String[] args) {
        int[] a = { 1, 4, 4, 5, 8, 19, 23, 42, 73 };
        int[] b = { 1, 4, 5, 9, 17, 21, 42, 73 };

        Arrays.sort(a); // Ensure array 'a' is sorted first.
        Arrays.sort(b); // Ensure array 'b' is sorted first.

        int[] c = intersection(a, b);

        System.out.println(Arrays.toString(c)); // [1, 4, 4, 5, 42, 73]
    }
}

Answer 2

我不喜欢我的解决方案。但这就是我得到的。

@Test
public void intersection() {
    List<Integer> a = new ArrayList<>(Arrays.asList(1, 4, 4, 5, 8, 19, 23, 42, 73));
    List<Integer> b = new ArrayList<>(Arrays.asList(1, 4, 5, 9, 17, 21, 42, 73, 99, 102));

    List<Integer> intersection = new ArrayList<>();
    findIntersection(intersection, a, b);
    assertThat(intersection, containsInAnyOrder(1, 4, 4, 5, 42, 73));
}

private void findIntersection(List<Integer> intersection, List<Integer> a, List<Integer> b) {
    if(!a.isEmpty()) {
        int i = a.remove(0);
        if(b.contains(i))
            intersection.add(i);
        findIntersection(intersection, a, b);
    }
}

Answer 3

虽然不是很漂亮，但对我来说最紧的版本：

public static int[] arrayIntersection(int[] a, int[] b) {
    if(a.length == 0 || b.length == 0)
        return new int[0];
    else {
        if(arrayContains(Arrays.copyOf(b, b.length-1), a[a.length-1]))
            return append(arrayIntersection(Arrays.copyOf(a, a.length-1), b), a[a.length-1]);
        else
            return arrayIntersection(Arrays.copyOf(a, a.length-1), b);
    }
}

private static boolean arrayContains(int[] a, int b) {
    if(a.length == 0) 
        return false;
    else {
        if(a[a.length-1] == b)
            return true;
        else
            return arrayContains(Arrays.copyOf(a, a.length-1), b);
    }
}

private static int[] append(int[] a, int b) {
    int[] res = Arrays.copyOf(a, a.length+1);
    res[res.length-1] = b;
    return res;
}

没有循环的整数数组交集递归

Integer array intersection recursion without loop

java

arrays

int

recursion

intersect

输入数组

预期输出（交集数组）