🧊陣列應用: 轉成2D陣列 Convert 1D Array Into 2D Array_Leetcode 2022

Karsten Winegeart on Unsplash

題目敘述 Convert 1D Array Into 2D Array

給定一個一維輸入陣列，請轉換成高度為m*寬度為n的二維陣列，
以二維陣列的形式輸出。

如果無法轉換，請輸出空陣列。

示意圖

測試範例

Example 1:

Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2],[3,4]]
Explanation: The constructed 2D array should contain 2 rows and 2 columns.
The first group of n=2 elements in original, [1,2], becomes the first row in the constructed 2D array.
The second group of n=2 elements in original, [3,4], becomes the second row in the constructed 2D array.

Example 2:

Input: original = [1,2,3], m = 1, n = 3
Output: [[1,2,3]]
Explanation: The constructed 2D array should contain 1 row and 3 columns.
Put all three elements in original into the first row of the constructed 2D array.

Example 3:

Input: original = [1,2], m = 1, n = 1
Output: []
Explanation: There are 2 elements in original.
It is impossible to fit 2 elements in a 1x1 2D array, so return an empty 2D array.

約束條件

Constraints:

• 1 <= original.length <= 5 * 10^4

輸入陣列的高度介於1~五萬之間。

• 1 <= original[i] <= 105

輸入陣列的寬度介於1~五萬之間。

• 1 <= m, n <= 4 * 10^4

二維陣列的高和寬都介於1~四萬之間。

演算法 List comprehension

根據指定的高度和寬度，計算是否可以相容轉換?

如果不行，直接輸出空陣列[]。

        # total element count of input array
        element_count = len(original)
        
        if element_count != m * n:
            
            # Reject if element count mismatch with new 2D array
            return []

如果可以，根據列表推導式直接轉換成對應的二維陣列即可。

程式碼 List comprehension

class Solution:
    def construct2DArray(self, original: List[int], m: int, n: int) -> List[List[int]]:
        
        # total element count of input array
        element_count = len(original)
        
        if element_count != m * n:
            
            # Reject if element count mismatch with new 2D array
            return []
        
        # reshape to specified 2D array by list comprehension
        return [ original[y*n:y*n+n] for y in range(m)]

複雜度分析

時間複雜度: O(m*n)

每個陣列元素搬移一次，總共m*n個元素。

空間複雜度: O(m*n)

每個陣列元素需要一個新的空間，總共m*n個元素。

Reference

[1] Convert 1D Array Into 2D Array - LeetCode

[2] List comprehension 列表推導式