题目地址：https://leetcode.com/problems/reshape-the-matrix/description/
题目描述
InMATLAB, there is a very useful function called 'reshape', which can reshape a matrix into a new one with different size but keep its original data.
You're given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.
Thereshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.
Ifthe 'reshape' operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
Example 1:
Input:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
Output:
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
Example 2:
Input:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
Output:
[[1,2],
[3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.
Note:
1、 Theheightandwidthofthegivenmatrixisinrange[1,100].；
2、 Thegivenrandcareallpositive.；
题目大意
实现Matlab的reshape函数，就是把原来的数组逐行遍历重新改成r行，c列，如果不能实现的话就是返回原来的数组。
解题方法
变长数组
Python的list是可变的，那么一个简单的想法就是使用可变的List作为新的一行，如果新的一行的元素个数等于题目要求的列数，那么就新建一行。把每行的结果放到返回的列表中即可。
时间复杂度是O(mn)，空间复杂度是O(1).没有额外空间
class Solution(object):
def matrixReshape(self, nums, r, c):
"""
:type nums: List[List[int]]
:type r: int
:type c: int
:rtype: List[List[int]]
"""
M, N = len(nums), len(nums[0])
if M * N != r * c:
return nums
res = []
row = []
for i in range(M):
for j in range(N):
row.append(nums[i][j])
if len(row) == c:
res.append(row)
row = []
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
求余法
这个做法是由位图法激发出来的，使用一个变量count保存现在已经有了的元素数量，那么直接可以使用res[count / c][count % c]确定轮到了的元素的位置。这个方法需要把数组提前构造好。
时间复杂度是O(mn)，空间复杂度是O(1).没有额外空间
class Solution(object):
def matrixReshape(self, nums, r, c):
"""
:type nums: List[List[int]]
:type r: int
:type c: int
:rtype: List[List[int]]
"""
M, N = len(nums), len(nums[0])
if M * N != r * c:
return nums
res = [[0] * c for _ in range(r)]
count = 0
for i in range(M):
for j in range(N):
res[count / c][count % c] = nums[i][j]
count +=1
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
维护行列
上面的方法每次需要通过除法和求余来确定新的位置，事实上是比较耗时的。更快的方法就是维护行和列的变量，在遍历的过程中更新行和列，这样就可以对应放入的位置了。
时间复杂度是O(mn)，空间复杂度是O(1).没有额外空间
class Solution(object):
def matrixReshape(self, nums, r, c):
"""
:type nums: List[List[int]]
:type r: int
:type c: int
:rtype: List[List[int]]
"""
M, N = len(nums), len(nums[0])
if M * N != r * c:
return nums
res = [[0] * c for _ in range(r)]
row, col = 0, 0
for i in range(M):
for j in range(N):
if col == c:
row += 1
col = 0
res[row][col] = nums[i][j]
col += 1
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
相似题目
参考资料
https://leetcode.com/articles/reshape-the-matrix/
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发