递归地过滤奇数-Java 学习之路

您将如何解决以下任务：编写一个递归方法，该方法传递一个数组，过滤所有奇数并将它们存储到一个数组中 . 返回的数组必须按每个元素顺序排序 . 您不允许使用任何提供的方法，如Arrays.sort，Lists等Java类 . 此外，不允许使用循环，并且通用的已知排序算法也适用于结果 .

过滤的部分很简单，但我不知道如何将每个元素放在正确的位置 . 目前，我的方法只返回一个包含所有奇数的未排序数组 .

public static int[] filterOdd(int[] m){
    return filterOdd(m, 0, 0);
}

private static int[] filterOdd(int[] m, int idx, int idxToPlace){
    if(idx <= m.length -1){
        if(m[idx] % 2 == 0){
            return filterOdd(m, idx + 1, idxToPlace);
        }else{
            int[] buffer = filterOdd(m, idx + 1, idxToPlace + 1);
            buffer[idxToPlace] = m[idx];
            return buffer;
        }
    }else{
        return new int[numberOfOddIntegers(m)];
    }
}

有没有办法递归地在正确的位置插入奇数？

2 回答

0

在您执行 buffer[idxToPlace] = m[idx]; 的地方，您必须调用另一个方法，该方法将返回已添加当前处理编号的已排序数组 .

这个新方法也可以递归：你知道那时你手中的数组是有序的 . 您只是递归遍历（例如从结尾到开始）并且从元素适合的那一刻开始（例如，小于前一个元素），您可以插入它并返回已排序的数组 . 如果只有1个元素（基本情况），您可以返回它 .

这样，在算法结束时，列表将被排序 .

回复于 2024-04-27T09:18:13+08:00

我不允许使用System.arraycopy

这意味着您需要计算出您将拥有多少个奇数，以便正确调整结果大小：

public static int[] filterOdd(int[] m){
    int[] res = new int[countOdd(m, 0)];
    filterOdd(m, 0, 0, res);
    return res;
}

private static int countOdd(int[] m, int i) {
    if (i == m.length) {
        return 0;
    }
    int isOdd = m[i] % 2 != 0 ? 1 : 0;
    return isOdd + countOdd(m, i+1);
}

private static void filterOdd(int[] m, int src, int dest, int[] res){
    if(src == m.length) {
        return;
    }
    if (m[src] % 2 != 0) {
        res[dest++] = m[src];
    }
    filterOdd(m, src+1, dest, res);
}

回复于 2024-04-27T09:18:13+08:00

递归地过滤奇数

2 回答

相关问题