如何统计int数组中连续相等值并返回计数与值顺序数组

核心实现思路 #

整体逻辑为单次遍历数组完成分段标记，无嵌套循环，时间复杂度O(n)，空间复杂度O(k)（k为连续分段的总数量），具体步骤如下：

• 先做边界判断：如果输入数组为空或者长度为0，直接返回两个空int数组即可
• 由于分段总数在遍历前无法确定，先用两个动态列表分别存储分段计数结果和分段对应值结果，遍历完成后再转成固定长度的int数组
• 初始化当前段的基准值为数组第一个元素，当前段的计数器初始值设为1
• 从数组下标为1的元素开始逐一遍历：
  • 若当前遍历元素和当前段基准值相等，直接给当前段计数器+1
  • 若不相等，说明当前段已经走到末尾：把当前段的计数值、基准值分别存入两个结果列表，再把基准值更新为当前遍历到的元素，计数器重置为1
• 整个数组遍历完成后，必须把最后一段的计数值和基准值存入结果列表——循环判断逻辑只会在遇到不同值时存储上一段，最后一段没有后续不同值触发存储，是最容易遗漏的步骤
• 最后把两个动态列表转为int数组返回即可

代码实现（Java版本，和示例语法对齐） #

import java.util.ArrayList;
import java.util.List;

public class ContinuousCount {
    public static int[][] countContinuousValue(int[] arr) {
        // 边界处理：空数组返回两个空数组
        if (arr == null || arr.length == 0) {
            return new int[][]{new int[0], new int[0]};
        }

        List<Integer> countList = new ArrayList<>();
        List<Integer> valueList = new ArrayList<>();

        // 初始化第一段参数
        int currentValue = arr[0];
        int currentCount = 1;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == currentValue) {
                currentCount++;
            } else {
                // 存储上一段的统计数据
                countList.add(currentCount);
                valueList.add(currentValue);
                // 更新为新段的初始参数
                currentValue = arr[i];
                currentCount = 1;
            }
        }
        // 补存最后一段的统计数据
        countList.add(currentCount);
        valueList.add(currentValue);

        // 列表转基础类型int数组
        int[] counts = countList.stream().mapToInt(Integer::intValue).toArray();
        int[] values = valueList.stream().mapToInt(Integer::intValue).toArray();

        return new int[][]{counts, values};
    }

    public static void main(String[] args) {
        int[] arr = {0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,0,0,0,1,1,1,2,2,2,2,0,0,0,0};
        int[][] result = countContinuousValue(arr);
        // 输出结果和预期完全一致：
        // 计数数组：[11,5,4,3,3,4,4]
        // 数值数组：[0,1,2,0,1,2,0]
    }
}

校验提示：将示例输入传入上述代码，输出的两个数组完全匹配预期结果，所有分段计数累加和等于原数组长度，不会出现统计遗漏。

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