LeetCode48/189 Rotate Image/Rotate Array-蒲公英云

LeetCode48/189 Rotate Image/Rotate Array

红太狼 2022-08-05 14:19 288阅读 0赞

一：Rotate Image

题目：

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

链接：https://leetcode.com/problems/rotate-image/

分析：这里我提供两种解法

法一：需要额外的空间复杂度O(MN),时间复杂度为O(MN)，旋转90度就是将[i,j]放在新数组的[j, n-1-i]位置处

int n = matrix.size();
       vector<vector<int> > tmp = matrix;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                matrix[j][n-i-1] = tmp[i][j];
            }
        }

法二：将一副图像旋转90度就是将其上下对折，然后再按照对角线对折，It is amazing！！时间复杂度仍然为O(MN)，但不需要额外的空间了。

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        int n = matrix.size();
       /* vector<vector<int> > tmp = matrix;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                matrix[j][n-i-1] = tmp[i][j];
            }
        }*/
        for(int i = 0; i < n; i++){  // 先上下对折
            for(int j = 0; j < n/2; j++)
                swap(matrix[i][j], matrix[i][n-1-j]);
        }
        for(int i = 0; i < n; i++){   // 后按照对角线对折就能顺时针旋转90度了
            for(int j = 0; j < n-1-i; j++)
                swap(matrix[i][j], matrix[n-1-j][n-i-1]);
        }
    }
};

二： Rotate Array

题目：

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

链接//leetcode.com/problems/rotate-array/

分析：这里仍提供两种方法，法一需要额外的空间O(N),法二利用对折就可以了，方法是先对折前面n-k个元素，然后对折后面k个元素，最后对折这n个元素就可以了，it is amazing！！

class Solution {
public:
    void rotate(int nums[], int n, int k) {
       /* k = k%n;
        int *a = new int[k];    // 需要空间复杂度O(k)
        for(int i = 0; i < k; i++)
            a[i] = nums[n-k+i];
        for(int i = n-k-1; i >= 0; i--)
            nums[i+k] = nums[i];
        for(int i = 0; i < k; i++)
            nums[i] = a[i];
        delete []a;*/
        k = k % n;
        for(int i = 0; i < (n-k)/2; i++)    // 先对折前面的n-k个元素
            swap(nums[i], nums[n-k-1-i]);
        for(int i = 0; i < k/2; i++)
            swap(nums[n-k+i], nums[n-1-i]);   // 对折后面的k个元素
        for(int i = 0; i < n/2; i++)
            swap(nums[i], nums[n-1-i]);       // 最后对折这n个元素
    }
};