Java中如何递归实现countDuplicates数组重复元素计数方法

首先明确原方法逻辑：输入为按字典序排好的字符串数组，统计相邻位置元素相等的次数，测试用例{"A", "A", "B", "C", "C", "C", "D"}中，相邻相等的位置为(0,1)、(3,4)、(4,5)，共3次，和预期输出一致。

改写思路 #

递归的核心是把线性遍历的逻辑拆分为「当前位置的判断」+「剩余子数组的同逻辑计算」：

• 先处理边界场景：输入为null、数组长度小于2时，不存在相邻元素，直接返回0
• 定义递归终止条件：当遍历到数组倒数第二个元素之后的位置，没有后续元素可以比较，返回0
• 单层递归逻辑：判断当前索引和下一个索引的元素是否相等，相等则当前贡献1个计数，否则贡献0，再加上从下一个索引开始的剩余数组的统计结果，就是总计数
• 为了避免递归过程中频繁复制数组，通过辅助递归方法传入当前遍历的索引位，把额外空间开销控制在递归栈级别

最终实现代码 #

public static int countDuplicates(String[] input) {
    // 边界场景直接返回
    if (input == null || input.length < 2) {
        return 0;
    }
    // 从索引0开始递归统计
    return doCountRecursively(input, 0);
}

/**
 * 递归辅助方法
 * @param input 待统计数组
 * @param currentIndex 当前待比较的索引位置
 * @return 从currentIndex开始到数组末尾的相邻重复次数
 */
private static int doCountRecursively(String[] input, int currentIndex) {
    // 递归终止：当前位置已经没有下一个元素可以比较
    if (currentIndex >= input.length - 1) {
        return 0;
    }
    // 统计当前位置和下一位是否相等
    // 注：原迭代代码用==比较字符串，仅在字符串为同一对象引用时生效，比较字符串内容建议用equals
    int currentPairCount = input[currentIndex].equals(input[currentIndex + 1]) ? 1 : 0;
    // 累加下一个位置开始的统计结果
    return currentPairCount + doCountRecursively(input, currentIndex + 1);
}

逻辑校验 #

传入测试用例{"A", "A", "B", "C", "C", "C", "D"}时，递归计算过程为：

1. 索引0：A和A相等，记1，加索引1的统计结果
2. 索引1：A和B不等，记0，加索引2的统计结果
3. 索引2：B和C不等，记0，加索引3的统计结果
4. 索引3：C和C相等，记1，加索引4的统计结果
5. 索引4：C和C相等，记1，加索引5的统计结果
6. 索引5：C和D不等，记0，加索引6的统计结果
7. 索引6：到达数组末尾，返回0

累加结果为1+0+0+1+1+0=3，完全符合预期输出。该实现时间复杂度和原迭代版本一致为O(n)，空间复杂度为递归栈带来的O(n)。

内容的提问来源于stack exchange，提问作者chhscs