LeetCode第251题：展平二维向量

题目描述

设计并实现一个迭代器，用于展平二维向量。该迭代器需要支持 next() 和 hasNext() 两个操作。

难度

中等

题目链接

示例

示例 1：

Vector2D vector2D = new Vector2D([[1,2],[3],[4]]);
vector2D.next();    // 返回 1
vector2D.next();    // 返回 2
vector2D.next();    // 返回 3
vector2D.hasNext(); // 返回 true
vector2D.hasNext(); // 返回 true
vector2D.next();    // 返回 4
vector2D.hasNext(); // 返回 false

提示

next() 和 hasNext() 操作的均摊时间复杂度为 O(1)。
最多会有 10^5 次对 next 的调用。

解题思路

方法：使用两个索引

我们需要设计一个能够遍历二维向量的迭代器。最直观的方法是使用两个索引：一个外部索引指向当前正在遍历的子向量，一个内部索引指向该子向量中的具体元素。

关键点

使用两个索引来追踪当前位置：行索引和列索引
实现next()方法来返回当前元素并将指针移到下一个元素
实现hasNext()方法来检查是否还有下一个元素
需要处理空向量的情况

具体步骤

在构造函数中初始化二维向量和两个索引（行和列）
实现hasNext()方法：
- 检查当前索引是否已经超出二维向量的范围
- 如果当前行是空的或者列索引已经到达当前行的末尾，则寻找下一个非空行
- 返回是否找到有效位置
实现next()方法：
- 确保有下一个元素可用
- 获取当前位置的元素
- 更新索引以指向下一个位置
- 返回获取的元素

复杂度分析

时间复杂度：
- 构造函数：O(1)
- next()：均摊O(1)。最坏情况下需要跳过多个空行，但平均每个元素只被访问一次。
- hasNext()：均摊O(1)，理由同上。
空间复杂度：O(1)，只使用了常数级别的额外空间。

图解思路

迭代器状态追踪表

操作	行索引	列索引	返回值	说明
初始化	0	0	-	指向第一个子向量的第一个元素
next()	0	1	1	返回[0][0]的元素，指针移到[0][1]
next()	1	0	2	返回[0][1]的元素，指针移到[1][0]
next()	2	0	3	返回[1][0]的元素，指针移到[2][0]
hasNext()	2	0	true	检查是否还有元素，有[2][0]
next()	3	0	4	返回[2][0]的元素，指针移到[3][0]（超出范围）
hasNext()	3	0	false	检查是否还有元素，没有了

特殊情况处理表

情况	处理方法	示例
空二维向量	hasNext()直接返回false	`[]`
包含空向量的二维向量	在hasNext()中跳过空向量	`[[],[1,2],[]]`
所有子向量都为空	hasNext()返回false	`[[],[],[]]`
已经遍历到最后一个元素	下一次hasNext()返回false	最后一次next()后

代码实现

C# 实现

public class Vector2D {
    private int[][] vectors;
    private int row;
    private int col;

    public Vector2D(int[][] vec) {
        vectors = vec;
        row = 0;
        col = 0;
        // 初始化时，如果当前行为空，就移动到下一个非空行
        MoveToNext();
    }
    
    public int Next() {
        // 确保有下一个元素
        if (!HasNext()) {
            throw new InvalidOperationException("No more elements");
        }
        
        // 获取当前元素
        int result = vectors[row][col];
        
        // 移动到下一个位置
        col++;
        MoveToNext();
        
        return result;
    }
    
    public bool HasNext() {
        // 检查是否还有有效位置
        return row < vectors.Length;
    }
    
    // 辅助方法，移动到下一个有效位置
    private void MoveToNext() {
        // 如果列索引超过当前行的长度，移动到下一行
        while (row < vectors.Length && col >= vectors[row].Length) {
            row++;
            col = 0;
        }
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D obj = new Vector2D(vec);
 * int param_1 = obj.Next();
 * bool param_2 = obj.HasNext();
 */

Python 实现

class Vector2D:
    def __init__(self, vec: List[List[int]]):
        self.vectors = vec
        self.row = 0
        self.col = 0
        # 初始化时，如果当前行为空，就移动到下一个非空行
        self._move_to_next()
    
    def next(self) -> int:
        # 确保有下一个元素
        if not self.hasNext():
            raise StopIteration("No more elements")
        
        # 获取当前元素
        result = self.vectors[self.row][self.col]
        
        # 移动到下一个位置
        self.col += 1
        self._move_to_next()
        
        return result
    
    def hasNext(self) -> bool:
        # 检查是否还有有效位置
        return self.row < len(self.vectors)
    
    # 辅助方法，移动到下一个有效位置
    def _move_to_next(self) -> None:
        # 如果列索引超过当前行的长度，移动到下一行
        while self.row < len(self.vectors) and self.col >= len(self.vectors[self.row]):
            self.row += 1
            self.col = 0

# Your Vector2D object will be instantiated and called as such:
# obj = Vector2D(vec)
# param_1 = obj.next()
# param_2 = obj.hasNext()

C++ 实现

class Vector2D {
private:
    vector<vector<int>> vectors;
    int row;
    int col;
    
    // 辅助方法，移动到下一个有效位置
    void moveToNext() {
        // 如果列索引超过当前行的长度，移动到下一行
        while (row < vectors.size() && col >= vectors[row].size()) {
            row++;
            col = 0;
        }
    }
    
public:
    Vector2D(vector<vector<int>>& vec) {
        vectors = vec;
        row = 0;
        col = 0;
        // 初始化时，如果当前行为空，就移动到下一个非空行
        moveToNext();
    }
    
    int next() {
        // 确保有下一个元素
        if (!hasNext()) {
            throw runtime_error("No more elements");
        }
        
        // 获取当前元素
        int result = vectors[row][col];
        
        // 移动到下一个位置
        col++;
        moveToNext();
        
        return result;
    }
    
    bool hasNext() {
        // 检查是否还有有效位置
        return row < vectors.size();
    }
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(vec);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

执行结果

C# 实现

执行用时：188 ms
内存消耗：46.8 MB

Python 实现

执行用时：64 ms
内存消耗：20.1 MB

C++ 实现

执行用时：24 ms
内存消耗：13.4 MB

性能对比

语言	执行用时	内存消耗	特点
C#	188 ms	46.8 MB	代码结构清晰，但相对较慢
Python	64 ms	20.1 MB	语法简洁，性能适中
C++	24 ms	13.4 MB	性能最佳，内存占用最小

代码亮点

🎯 核心算法使用两个指针（行和列）实现二维向量的遍历，思路清晰直观
💡 通过辅助方法moveToNext()统一处理空行跳过逻辑，避免代码重复
🔍 在构造函数中就进行初始位置调整，确保第一个next()调用能够正确返回元素
🎨 三种语言实现保持一致的算法思路，代码结构清晰，变量命名有意义

常见错误分析

🚫 忘记处理空向量的情况，导致数组越界异常
🚫 在next()方法中没有检查是否还有下一个元素，可能引发异常
🚫 忘记在获取元素后更新索引，导致重复返回相同元素
🚫 实现hasNext()时没有考虑跳过空向量的情况，可能错误地返回false

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
两个索引法	均摊O(1)	O(1)	实现简单，直观	需要处理多种边界情况
预处理展平	O(n) 初始化, O(1) 查询	O(n)	查询操作非常快	占用额外空间，不符合迭代器惰性求值的理念
队列实现	O(n) 初始化, O(1) 查询	O(n)	实现简单	占用额外空间

题目描述

难度

题目链接

示例

示例 1：

提示

解题思路

方法：使用两个索引

关键点

具体步骤

复杂度分析

图解思路

迭代器状态追踪表

特殊情况处理表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目