高效获取二维交错数组指定索引范围元素的方法与算法

问题定义 #

目标查询的二维交错数组结构如下：

• 第0行：[0,0] [0,1] [0,2]（长度3）
• 第1行：[1,0] [1,1]（长度2）
• 第2行：[2,0] [2,1] [2,2]（长度3）

需求为输入起止索引[rStart, cStart]、[rEnd, cEnd]，返回所有落在索引区间内的元素。示例：

• 查询区间[0,0]到[2,0]：返回区间覆盖的所有元素
• 查询区间[0,0]到[2,1]：预期覆盖索引为[0,0] [0,1] [0,2] [1,0] [1,1] [2,0] [2,1]

现成算法复用说明 #

目前没有针对不规则交错数组该场景的开箱即用内置算法。规则二维矩阵常用的前缀和、二维线段树等区间查询算法是为等长二维数组设计的，套用到交错数组上会产生大量冗余计算，不适合直接使用。

最优实现方案（C#） #

该需求的理论最优时间复杂度为O(k)，k为待返回的元素总数——毕竟必须逐个访问要返回的元素才能完成取值，不存在复杂度更低的方案。之前用基础for循环效率不理想，通常是边界判断逻辑冗余、额外分配不必要内存导致的。
可直接使用以下实现，无冗余遍历，内存开销极低：

public static IEnumerable<T> GetJaggedArrayRange<T>(T[][] jaggedArr, int rStart, int cStart, int rEnd, int cEnd)
{
    // 参数合法性校验
    if (jaggedArr == null) throw new ArgumentNullException(nameof(jaggedArr));
    if (rStart < 0 || rEnd >= jaggedArr.Length || rStart > rEnd)
        throw new ArgumentOutOfRangeException("行索引参数非法");

    for (int row = rStart; row <= rEnd; row++)
    {
        T[] currentRow = jaggedArr[row];
        if (currentRow == null || currentRow.Length == 0) continue;

        int colBegin, colRangeEnd;
        if (row == rStart)
        {
            colBegin = cStart;
            colRangeEnd = row == rEnd ? cEnd : currentRow.Length - 1;
        }
        else if (row == rEnd)
        {
            colBegin = 0;
            colRangeEnd = cEnd;
        }
        else
        {
            colBegin = 0;
            colRangeEnd = currentRow.Length - 1;
        }

        // 兼容行长度不足的越界场景
        colBegin = Math.Max(colBegin, 0);
        colRangeEnd = Math.Min(colRangeEnd, currentRow.Length - 1);
        if (colBegin > colRangeEnd) continue;

        for (int col = colBegin; col <= colRangeEnd; col++)
        {
            yield return currentRow[col];
        }
    }
}

实现说明 #

• 按行遍历区间覆盖的行范围，针对首行、中间行、尾行分别计算列的起止位置，不会遍历任何不需要返回的元素
• 用yield return做延迟迭代，不需要提前分配存储全部结果的集合内存，调用方可直接遍历返回值，或调用ToList()/ToArray()按需转换为集合
• 自带边界校验，兼容交错数组中存在空行、行长度小于预期列索引的异常场景

如果需要对同一个交错数组做超高频次的区间查询，可提前预处理每一行的切片访问入口，进一步减少每次查询时的列边界计算开销，单次查询的时间复杂度依然保持O(k)。

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