{"id":3547,"date":"2018-08-16T08:54:55","date_gmt":"2018-08-16T15:54:55","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3547"},"modified":"2018-08-16T08:55:23","modified_gmt":"2018-08-16T15:55:23","slug":"leetcode-566-reshape-the-matrix","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-566-reshape-the-matrix\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 566. Reshape the Matrix"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 566. Reshape the Matrix -  \u5237\u9898\u627e\u5de5\u4f5c EP7\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/tI8M9GO4Kvo?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1>Problem<\/h1>\n<p>In MATLAB, there is a very useful function called &#8216;reshape&#8217;, which can reshape a matrix into a new one with different size but keep its original data.<\/p>\n<p>You&#8217;re given a matrix represented by a two-dimensional array, and two\u00a0<b>positive<\/b>\u00a0integers\u00a0<b>r<\/b>\u00a0and\u00a0<b>c<\/b>\u00a0representing the\u00a0<b>row<\/b>\u00a0number and\u00a0<b>column<\/b>\u00a0number of the wanted reshaped matrix, respectively.<\/p>\n<p>The reshaped matrix need to be filled with all the elements of the original matrix in the same\u00a0<b>row-traversing<\/b>\u00a0order as they were.<\/p>\n<p>If the &#8216;reshape&#8217; operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"crayon:false\"><b>Input:<\/b> \r\nnums = \r\n[[1,2],\r\n [3,4]]\r\nr = 1, c = 4\r\n<b>Output:<\/b> \r\n[[1,2,3,4]]\r\n<b>Explanation:<\/b>\r\nThe <b>row-traversing<\/b> 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.\r\n<\/pre>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"crayon:false\"><b>Input:<\/b> \r\nnums = \r\n[[1,2],\r\n [3,4]]\r\nr = 2, c = 4\r\n<b>Output:<\/b> \r\n[[1,2],\r\n [3,4]]\r\n<b>Explanation:<\/b>\r\nThere is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>The height and width of the given matrix is in range [1, 100].<\/li>\n<li>The given r and c are all positive.<\/li>\n<\/ol>\n<h1>Solution1: Brute Force<\/h1>\n<p>Time complexity: O(mn)<\/p>\n<p>Space complexity: O(mn)<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 32 ms\r\nclass Solution {\r\npublic:\r\n    vector&lt;vector&lt;int&gt;&gt; matrixReshape(vector&lt;vector&lt;int&gt;&gt;&amp; nums, int r, int c) {\r\n        if (nums.size() == 0) return nums;\r\n        int m = nums.size();\r\n        int n = nums[0].size();\r\n        if (m * n != r * c) return nums;\r\n        \r\n        \/\/ new matrix r*c\r\n        vector&lt;vector&lt;int&gt;&gt; ans(r, vector&lt;int&gt;(c));\r\n        for(int i = 0; i &lt; m * n;++i) {\r\n            int src_y = i \/ n;\r\n            int src_x = i % n;\r\n            int dst_y = i \/ c;\r\n            int dst_x = i % c;\r\n            ans[dst_y][dst_x] = nums[src_y][src_x];\r\n        }\r\n        \r\n        return ans;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem In MATLAB, there is a very useful function called &#8216;reshape&#8217;, which can reshape a matrix into a new one with different size but keep&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[222,216,366,378],"class_list":["post-3547","post","type-post","status-publish","format-standard","hentry","category-array","tag-easy","tag-matrix","tag-omn","tag-reshape","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3547","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3547"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3547\/revisions"}],"predecessor-version":[{"id":3549,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3547\/revisions\/3549"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3547"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3547"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3547"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}