题目地址:https://leetcode.com/problems/reshape-the-matrix/description/

题目描述

在MATLAB中,有一个非常有用的函数 reshape,它可以将一个矩阵重塑为另一个大小不同的新矩阵,但保留其原始数据。
给出一个由二维数组表示的矩阵,以及两个正整数r和c,分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的reshape操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。

示例 1:
输入:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
输出:
[[1,2,3,4]]
解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。

示例 2:
输入:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
输出:
[[1,2],
[3,4]]
解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。

注意:

  1. 给定矩阵的宽和高范围在 [1, 100]。
  2. 给定的 r 和 c 都是正数。

解题思路

首先解决不满足条件的情况,即如果具有给定参数的reshape操作不是可行且合理的,输出原始矩阵。方法是判断原始矩阵的行列乘积与重塑后矩阵的行列乘积是否相等,不相等就返回原始矩阵,相等则进行重塑。

然后是重塑过程,因为要求重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充,所以先构建一个临时一维列表tempNums,将原始矩阵按行遍历并将每个原始矩阵中元素都暂时存入tempNums中,

重塑矩阵是rc列,即每行有c个元素,因此把tempNums数组中所有元素分割成长度为c的若干个小列表,分割方法为:

1
tempNums = [tempNums[i:i+c] for i in range(0,len(tempNums), c)]

最后构建重塑矩阵newNums,它有r行,因此循环r次,每行将tempNums中的长度为c的小列表加入,完成重塑。

通过代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def matrixReshape(self, nums, r, c):
"""
:type nums: List[List[int]]
:type r: int
:type c: int
:rtype: List[List[int]]
"""
row = len(nums)
col = len(nums[0])
if not row*col == r*c:
return nums
tempNums = []
for i in range(row):
for j in range(col):
tempNums.append(nums[i][j])
tempNums = [tempNums[i:i+c] for i in range(0,len(tempNums), c)]
newNums = []
for i in range(r):
newNums.append(tempNums[i])
return newNums

优化通过代码

了解了上面代码的思路后,使用itertools模块做进一步优化。首先是构建临时一维列表tempNums部分:用双重循环遍历原始矩阵中每个元素加入到tempNums。这一部分可以用itertools.chain优化。

1
tempNums = itertools.chain(*nums)

itertools.chain可以把一组迭代对象串联起来,形成一个更大的迭代器,比如对nums = [[1,2], [3,4]],形成新的大迭代器tempNums为[1,2,3,4]。

然后是上文中先把tempNums分割成长度为c的小列表,再通过循环放入各行,这段可以简化为一行代码:

1
[list(itertools.islice(tempNums, c)) for _ in range(r)]

itertools.islice类似于slice()函数,可以指定起始位置和步长,itertools.islice(it, c)的作用是将迭代器tempNums按步长为c划分,然后循环r次。

语句中for _ in range(r),其中的_是个变量,但是无需关注其实际含义的变量,也就是不需要引用计数值,也不用给这个计数值起名字,用_代替i,实现循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import itertools
class Solution:
def matrixReshape(self, nums, r, c):
"""
:type nums: List[List[int]]
:type r: int
:type c: int
:rtype: List[List[int]]
"""
if r * c != len(nums) * len(nums[0]):
return nums
tempNums = itertools.chain(*nums)
return [list(itertools.islice(tempNums, c)) for _ in range(r)]

另外还有一种有意思的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import itertools
class Solution:
def matrixReshape(self, nums, r, c):
"""
:type nums: List[List[int]]
:type r: int
:type c: int
:rtype: List[List[int]]
"""
if r * c == len(nums) * len(nums[0]):
ret = []
tempNums = list(itertools.chain(*nums))
for i in range(r):
ret.append(tempNums[i*c:(i+1)*c])
return ret
else:
return nums

ret.append(tempNums[i*c:(i+1)*c])tempNums分成r行c列的思路自己没想到。