在我的最新作业中，我应该使用递归和没有循环找到两个整数数组之间的交点（可能也没有专门的方法，但没有指定）。
输入阵列
-
[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 + "nn");
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);
}
但这可以多次检查相同的对，因此产生的输出太长了。
帮助我堆叠溢出，您是我唯一的希望。
虽然不是很漂亮，但对我来说最紧张的版本：
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;
}
解决这个问题的最微不足道的方法是首先找出哪个数组更长。
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]
}
}
我不喜欢我的解决方案。但这就是我得到的。
@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);
}
}