Rotate a matrix represented in a 1D vector by 90 degrees

user_14798472 0
Viewed 142

I want to rotate a matrix by 90 degrees in place represented in the form of a 1D vector.

When it is in 2D, this is what I did that works:

void rotate(vector<vector<int>>& matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i){
        for (int j= i + 1; j < matrix[0].size(); ++j) {
            swap(matrix[i][j], matrix[j][i]);
        }
    }
}

When I represent it in 1D, for example:

vector<int> matrix = {1, 2, 3, 4, 5, 6, 7, 8, 9};

This is what I tried:

void rotate(vector<int>& matrix, const int& n) {
    int i = 0, j = 0;
    for (i = 0; i < n; ++i) {
        for (j = i + 1; j < n; ++j) {
            swap(matrix[i + j], matrix[i + j * n]);
        }
        reverse(matrix.begin() + i * n, matrix.begin() + (i * n) + j);
    }
}

The result was:

matrix = {7, 4, 1, 6, 5, 8, 9, 2, 3}

But the expected result should be:

matrix = {7, 4, 1, 8, 5, 2, 9, 6, 3}

Is there a better way to do this or what am I missing, in terms of indexing?

vector matrix c++
1 Answers

You almost got it.

At this line:

swap(matrix[i + j], matrix[i + j * n]);

Your first indexing should be i * n + j. That's basically the "formula" to convert 2D indices into 1D (for square matrices only). So, matrix[i][j] becomes matrix[i * n + j]. The same thing applies in reverse: matrix[j][i] becomes matrix[j * n + i], just like you did originally on the second swap parameter.

Lastly, at this line:

reverse(matrix.begin()+i*n, matrix.begin() + (i*n)+ j);

The last expression should be (i * n) + n.

To explain this, you can walk through the code. Assuming we reached the second reverse, after the inner loop finished, and we're at the second iteration of the outer loop (i = 1). The array will look something like this before the reverse:

. . . 2 5 8 . . .

And we want to reverse this group to this:

. . . 8 5 2 . . .

Now in order to reverse just that middle part, we need to get the index range for these three numbers.

The start index would be i * n or 1 * 3 = 3 in this case and (i * n) + n (or (i + 1) * n) which would evaluate to (1 * 3) + 3 = 6, representing the end index correctly.

user_2604110
Related