X

LEETCODE 251. Flatten 2D Vector 解题思路分析

题目大意:

展开二维向量

请设计并实现一个能够展开二维向量的迭代器。该迭代器需要支持 nexthasNext 两种操作。

示例:

Vector2D iterator = new Vector2D([[1,2],[3],[4]]);

iterator.next(); // 返回 1
iterator.next(); // 返回 2
iterator.next(); // 返回 3
iterator.hasNext(); // 返回 true
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 4
iterator.hasNext(); // 返回 false

注意:

  1. 请记得 重置 在 Vector2D 中声明的类变量(静态变量),因为类变量会 在多个测试用例中保持不变,影响判题准确。请 查阅 这里。
  2. 你可以假定 next() 的调用总是合法的,即当 next() 被调用时,二维向量总是存在至少一个后续元素。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=251

解题思路分析:

题目给出了一个二维数组,不过需要注意一点,该二维数组每一行的元素个数不一定相同,因此,在构造函数中,我们可以先将二维数组转化为一维数组,之后在一维数组中做查找即可。

实现代码:

int[] arr; // 一维数组
int index=0; // 当前下标
public Vector2D(int[][] v) {
    // 查看二维数组中总共的元素个数
    int count=0;
    for(int[] a : v){
        count+=a.length;
    }
    // 利用元素个数初始化一维数组
    arr=new int[count];
    int i=0;
    // 将二维数组转化为一维数组
    for(int[] a : v){
        for(int num : a){
            arr[i++]=num;
        }
    }
}

public int next() {
    // 从一位数组中取出当前下标的值,同时index加一
    return arr[index++];
}

public boolean hasNext() {
    // 返回当前下标是否小于数组长度
    return index<arr.length;
}

本题解法执行时间为11ms。

Runtime: 11 ms, faster than 93.92% of Java online submissions for Flatten 2D Vector.

Memory Usage: 57.4 MB, less than 5.55% of Java online submissions for Flatten 2D Vector.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-251-flatten-2d-vector-解题思路分析/
Categories: leetcode
kwantong: