10k

251. Flatten 2D Vector

Published on

Question

This question is about an array containing arrays of varying lengths, and implementing one of its next() methods and hasNext() methods. (For two-dimensional arrays, Java itself does not support these two methods)

It is best to use Java's own Iterator implementation. (ps: this place is rather strange ha, after the topic why this place is rather strange).

Algorithm

The first thing I thought was to iterate through the array and the small arrays in it, and just keep taking the numbers out. The first time, I took it for granted that the array was an array with all subarrays of equal length, so I was wrong the first time.

The second time I tried to implement it, but I couldn't get it right. So I put down this topic for a day.

This morning when I went to do this question again, referring to his topic said to use iterators to achieve a little, so I did as code 1 in the code, and quickly came out.

This place with the iterator feels redundant, so and the standard answer says that this overall method of changing the input is not good, never change the input is best. And if we only take the data in front, then it is a waste of time to traverse the whole array and save it to the list or iter.

After reading the discussion, it should be that the original input is an array list, but now it's changed to an array array. So the last sentence with Iterator to achieve this looks abrupt and strange.

So how to optimize or a different way to take the implementation?

In fact, it's still the same idea I started with on the first day and re-executed it, referring to the standard answer. next() is to keep taking values down, when an array is taken (that is, inner index reaches the length of the current sub-array outer < vector.length && inner == vector[outer].length), at this time you can let outer index go back one, and set inner to 0, and we'll traverse the new next subarray. The hasNext() method also needs to do some judging and forward work in order to exclude the empty subarrays until it encounters an array with a number or the outer index reaches the end.

There are two small points of attention here, the first is that he used outer and inner, so than when I first wrote with m, n will be much clearer, reducing the burden of thinking, especially if you have to deal with the relationship between inside and outside when you have a meeting m, n is what. Another point is that this input has an empty array of inputs, and more than one may be consecutive, so there is a step in the checknext or hasNext operation is to skip the content of these no numbers, so this place will have a while loop. If I hadn't read the hint the second time I wrote it, I would have written if.

Code 1

class Vector2D {
    Iterator iter;

    public Vector2D(int[][] vec) {
        List<Integer> list = new ArrayList<>();
        for (int[] vals : vec) {
            for (int val : vals) {
                list.add(val);
            }
        }
        iter = list.iterator();
    }
    
    public int next() {
        return (int) iter.next();
    }
    
    public boolean hasNext() {
        return iter.hasNext();
    }
}

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

Time complexity.

  • constructor: O(N+V), N is the length of all elements, V is the outer index, i.e. the number of subarrays.
  • next() & hasNext() :O(1)

Space complexity.

  • Constructor: O(N)

Code 2

class Vector2D {
    private int[][] vector;
    int outer;
    int inner;

    public Vector2D(int[][] vec) {
        vector = vec;
        inner = 0;
        outer = 0;
    }
    
    public int next() {
        if (hasNext()) {
            while (outer < vector.length && inner == vector[outer].length) {
                outer++;
                inner = 0;
            } // this function could be extracted to a common used function;
            return vector[outer][inner++];
        }   
        return 501; // we could throw a NoSuchElementException() here;
    }
    
    public boolean hasNext() {
        while (outer < vector.length && inner == vector[outer].length) {
            outer++;
            inner = 0;
        }
        return outer ! = vector.length;
    }
}

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

Time complexity.

  • constructor: O(1)
  • next() & hasNext() :O(1)

Space complexity: O(1), we use a constant order of magnitude of extra space

题目

这个题目是说，一个数组，里面包含长度不一的数组，自己实现他的一个next()方法和hasNext()方法。（对于二维数组，Java本身没有支持这两个方法）

最好用Java自带的Iterator实现一下。（ps: 这个地方比较奇怪哈，后面讲题目这个地方为什么比较奇怪）。

解析

我最开始的思路是通过遍历数组和其中的小数组，不断地将数字取出来即可。第一遍的时候竟然想当然的将数组当成了一个所有子数组都是长度相当的，所以第一遍就错了。

第二遍的时候尝试去实现，却是搞不对。所以暂时就放下了一天这个题目。

今天早上再去做这个题的时候，参照他题目中说用迭代器实现一下，所以就做了如代码1中的代码，很快就出来了。

这个地方用迭代器感觉很多余，所以而且标准答案说这种整体的改变输入的方法不好，永远不要改变输入最好。而且如果是我们只取前面的数据，那遍历整个数组转存到list中或者iter中就是浪费时间。

后面看了discussion，应该是原来的输入是数组列表，现在改成了数组数组。所以最后一句用Iterator实现这个看起来突兀且奇怪了。

所以怎么优化或者是换一种方法取执行呢？

其实还是我第一天最开始的思路，重新执行了一遍，参考了标准答案。next()就是不断往下取值，当一个数组取完之后（即inner index达到了当前子数组的长度outer < vector.length && inner == vector[outer].length），此时可以让outer index向后走一位，并将inner置为0，我们要遍历新的下一个子数组了。hasNext()方法同样为了排除空子数组，需要先做一些判断和前进的工作，直到遇到了有数字的数组或者outer index到达最后。

这里有两个注意的小点，第一就是他用了outer和inner，这样比我最开始写的时候用m，n会清晰很多，减少了思考的负担，尤其是你有处理内外的关系的时候你还有会议m、n是什么。另外一点就是，这个输入的输入存在着空数组，而且不止一个还可能连续，所以在检查next或者hasNext的时候有一步操作就是要跳过这些没有数字的内容，所以这个地方会有一个while循环。我最第二次写的时候如果没看提示可能会写成if。

代码1

class Vector2D {
    Iterator iter;

    public Vector2D(int[][] vec) {
        List<Integer> list = new ArrayList<>();
        for (int[] vals : vec) {
            for (int val : vals) {
                list.add(val);
            }
        }
        iter = list.iterator();
    }
    
    public int next() {
        return (int) iter.next();
    }
    
    public boolean hasNext() {
        return iter.hasNext();
    }
}

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

时间复杂度：

  • 构造函数：O(N+V), N是所有元素的长度，V是outer index，即子数组的数量。
  • next() & hasNext() :O(1)

空间复杂度：

  • 构造函数： O(N)

代码2

class Vector2D {
    private int[][] vector;
    int outer;
    int inner;

    public Vector2D(int[][] vec) {
        vector = vec;
        inner = 0;
        outer = 0;
    }
    
    public int next() {
        if (hasNext()) {
            while (outer < vector.length && inner == vector[outer].length) {
                outer++;
                inner = 0;
            } // this function could be extracted to a common used function;
            return vector[outer][inner++];
        }   
        return 501; // we could throw a NoSuchElementException() here;
    }
    
    public boolean hasNext() {
        while (outer < vector.length && inner == vector[outer].length) {
            outer++;
            inner = 0;
        }
        return outer != vector.length;
    }
}

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

时间复杂度：

  • 构造函数：O(1)
  • next() & hasNext() :O(1)

空间复杂度：O(1)，我们使用了常数量级的额外空间

Thoughts? Leave a comment