numOfColors 递归函数 JAVA

Question

我试图用Java编写递归函数。

该函数需要为我计算数组中的所有差异值。

即

{{1,1,1,1},{4,4,4,4},{3,3,1,1}}

递归函数返回 3 （1,4,3）

这是我需要编写的函数：

int numOfColors(int[][] map) 

我尝试过什么：

public static int numOfColors(int[][] arr) {
    int i=0;
    int j=0;
    int colors=0;
    int contains = arr[i][j];
    if (arr== null) { 
        return 0;
    } else if (arr[i][j] != 0&& arr[i][j]!=contains) { 
        colors ++;
    }
    return numOfColors(arr) + 1;
}

线程"main"中的异常 java.lang.StackOverflowError

我该如何解决它？

谢谢！

Answer 1

下面是使用递归且不使用任何Set或List查找唯一值计数的一种方法 -

package test;
public class Main {
    public static void main(String[] args) {
        int[][] arr = { { 4, 2, 2, 1, 4 }, { 4, 4, 3, 1, 4 }, { 1, 1, 4, 2, 1 }, { 1, 4, 0, 2, 2 }, { 4, 1, 4, 1, 1 } };
        System.out.println(numOfColors(arr));
    }
    public static int numOfColors(int[][] arr) {
        int unique = 0;
        if (arr.length == 0) {
            return unique;
        } else {
            int[] subArr = arr[arr.length - 1];
            outerLoop: for (int i = 0; i < subArr.length; i++) {
                int j = i + 1;
                for (; j < subArr.length; j++) {
                    if (subArr[i] == subArr[j]) {
                        break;
                    }
                }
                if (j == subArr.length) {
                    int k = 0;
                    for (; k < arr.length - 1; k++) {
                        for (int l = 0; l < arr[k].length; l++) {
                            if (subArr[i] == arr[k][l]) {
                                continue outerLoop;
                            }
                        }
                    }
                    if (k == arr.length - 1) {
                        unique++;
                    }
                }
            }
            int[][] dest = new int[arr.length - 1][];
            System.arraycopy(arr, 0, dest, 0, arr.length - 1);
            unique += numOfColors(dest);
            return unique;
        }
    }
}

输出
5

请注意，这个问题可以在没有递归的情况下轻松解决。此外，上面的代码可以使用Set

Answer 2

您可以使用递归帮助程序函数来删除重复项。

import java.util.*;
public class Main {
    public static void main(String[] strg) {
        int[][] arr = {{1, 1, 1, 1}, {4, 4, 4, 4}, {3, 3, 1, 1}};
        numOfColors(arr);
    }
    static int numOfColors(int[][] map) {
        ArrayList<Integer> intlist = new ArrayList<Integer>();
        for (int o = 0; o < map.length; o++) {
            for (int n = 0; n < map[o].length; n++) {
                intlist.add(map[o][n]);
            }
        }
        intlist = removeDuplicates(intlist, 0);
        System.out.println(intlist.size()+" " +intlist);
        return intlist.size();
    }
    static ArrayList<Integer> removeDuplicates(ArrayList<Integer> list, int counter) {
        if (list == null) {
            throw new NullPointerException();
        }
        if (counter < list.size()) {
            if (list.contains(list.get(counter))) {
                if (list.lastIndexOf(list.get(counter)) != counter) {
                    list.remove(list.lastIndexOf(list.get(counter)));
                    counter--;
                }
            }
            removeDuplicates(list, ++counter);
        }
        return list;
    }
}

输出

3 [1, 4, 3]

在线演示

Answer 3

我认为

在这种情况下不需要递归，所以我将解释我的方式。我将 arr 称为数组 A。 首先，你创建一个你已经看到的数字的哈希集，我们称之为哈希集 B。 然后，您可以遍历数组 A，处理每个元素。 检查哈希集 B 是否包含该元素。 如果是，请继续，如果没有，请将该值添加到哈希集 B。 循环后，返回哈希集 B 的长度，或者如果要查看唯一值是什么，则返回整个集合的长度。

例如：

import java.util.HashSet;
public class Class {
        public static void main(String[] args){
                int[][] A = {{1, 1, 1, 1}, {4, 4, 4, 4}, {3, 3, 1, 1}};
                System.out.println("Number of different values: " + countUniqueVals(A));
        }
        public static int countUniqueVals(int[][] A){
                HashSet<Integer> B = new HashSet<Integer>();
                for (int row = 0; row < A.length; row++)
                        for (int col = 0; col < A[row].length; col++)
                                B.add(A[row][col]);
                return B.size();
        }
}