Рекурсия пересечения целочисленного массива без цикла

В моем последнем задании я должен найти пересечение между двумя целочисленными массивами, используя рекурсию и без циклов (вероятно, также без специальных методов, но это не указано).

Входные массивы

  • [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, ты моя единственная надежда.


java arrays recursion int intersect
person Kusko25    schedule 02.12.2016    source источник
comment
Разве это не должно быть вашим ожидаемым результатом: [1, 4, 5, 42, 73] ?   -  person Mr. Polywhirl    schedule 02.12.2016
comment
Число 4 встречается дважды в исходном массиве и в результате встречается дважды для пересечения. Это ожидаемо и разрешено   -  person Kusko25    schedule 02.12.2016
comment
Возможный дубликат Java, найти пересечение двух массивов   -  person xenteros    schedule 02.12.2016

Ответы (3)


arrow_upward
0
arrow_downward

Самый простой способ сделать это — сначала выяснить, какой массив длиннее.

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]
    }
}
person Mr. Polywhirl    schedule 02.12.2016

arrow_upward
1
arrow_downward

хоть и не очень красиво, но для меня самый тугой вариант:

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;
}
person Level147    schedule 03.12.2016

arrow_upward
0
arrow_downward

Мне не понравилось мое решение. Но это то, что я получил.

@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);
    }
}
person Tomazini    schedule 02.12.2016