java - 计算数组中不同元素数量的递归方法

Question

假设我有这个数组:ARR = {5, 7, 3, 3, 7, 5} 我也有大小(在本例中为 6)，因此递归函数应返回 3。

这是函数/方法的声明:

int f(arr, size);

我试过这个东西:

count = 0;
if(size == 1)
   return 1;
if(x[i] != f(arr, size-1)
    count++;

return count;

但它不起作用，因为 f(arr, size-1) 不会遍历数组的所有元素并进行比较。

希望大家能帮上忙!

Answer 1

这是一种方法:

private static int f(int[] arr, int size) {
    if (size <= 1) return 0; // there can't be duplicates if there are not even 2 elements!
    return f(arr, size - 1) + (inArray(arr, size - 1, arr[size - 1]) ? 1 : 0);
}

private static boolean inArray(int[] arr, int size, int elem) {
    if (size == 0) return false;
    return arr[size - 1] == elem || inArray(arr, size - 1, elem);
}

基本上逻辑是这样的:

• size 表示我们真正关心的 arr 中的前 N ​​个元素。
• 如果 size 小于 2，我们知道不会有任何重复项，因此返回 0。
• 现在对于递归情况，我们返回 1 或 0，这取决于最后一个元素是否在数组的其余部分中，加上数组其余部分中重复项的数量(“最后一个元素”表示 array[size - 1] 和“其余”表示使用 size - 1 调用函数。)
• 判断一个元素是否在数组中，我也使用了递归的方法，思路类似(检查最后一个元素是否为elem，然后检查其余是否包含元素).