{"id":5698,"date":"2019-10-02T09:20:55","date_gmt":"2019-10-02T16:20:55","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5698"},"modified":"2019-10-02T09:21:29","modified_gmt":"2019-10-02T16:21:29","slug":"leetcode-48-rotate-image","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-48-rotate-image\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 48. Rotate Image"},"content":{"rendered":"\n<p>You are given an&nbsp;<em>n<\/em>&nbsp;x&nbsp;<em>n<\/em>&nbsp;2D matrix representing an image.<\/p>\n\n\n\n<p>Rotate the image by 90 degrees (clockwise).<\/p>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<p>You have to rotate the image&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/In-place_algorithm\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>in-place<\/strong><\/a>, which means you have to modify the input 2D matrix directly.&nbsp;<strong>DO NOT<\/strong>&nbsp;allocate another 2D matrix and do the rotation.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">Given <strong>input matrix<\/strong> = \n[\n  [1,2,3],\n  [4,5,6],\n  [7,8,9]\n],\n\nrotate the input matrix <strong>in-place<\/strong> such that it becomes:\n[\n  [7,4,1],\n  [8,5,2],\n  [9,6,3]\n]\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">Given <strong>input matrix<\/strong> =\n[\n  [ 5, 1, 9,11],\n  [ 2, 4, 8,10],\n  [13, 3, 6, 7],\n  [15,14,12,16]\n], \n\nrotate the input matrix <strong>in-place<\/strong> such that it becomes:\n[\n  [15,13, 2, 5],\n  [14, 3, 4, 1],\n  [12, 6, 8, 9],\n  [16, 7,10,11]\n]<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: 2 Passes<\/strong><\/h2>\n\n\n\n<p>First pass: mirror around diagonal <br>Second pass: mirror around y axis<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  void rotate(vector<vector<int>>& matrix) {\n    const int n = matrix.size();\n    for (int i = 0; i < n; ++i)\n      for (int j = i + 1; j < n; ++j)\n        swap(matrix[i][j], matrix[j][i]);\n    for (int i = 0; i < n; ++i)\n      reverse(begin(matrix[i]), end(matrix[i]));\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an&nbsp;n&nbsp;x&nbsp;n&nbsp;2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image&nbsp;in-place, which means you&#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":[20,302,273,216,177,349,498,250],"class_list":["post-5698","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-flip","tag-in-place","tag-matrix","tag-medium","tag-mirror","tag-on2","tag-rotate","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5698","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=5698"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5698\/revisions"}],"predecessor-version":[{"id":5701,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5698\/revisions\/5701"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5698"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5698"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5698"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}