patterncppMinor
Rotate image 90 degree clockwise
Viewed 0 times
degreerotateimageclockwise
Problem
* Time complexity: O(N)
* Memory complexity: \$O(1)\$
Is my calculation of complexity correct for this code?
* Memory complexity: \$O(1)\$
Is my calculation of complexity correct for this code?
#include
#include
#include
using namespace std;
using Vector = vector>;
int main()
{
const size_t SIZE = 7;
Vector image(SIZE, vector(SIZE));
cout << "******* original image ******" << endl;
int value = 0;
for (auto& i : image)
{
for (auto& j : i)
{
cout << (j = value) << ' ';
}
value++;
cout << '\n';
}
// rotate image 90 degree clockwise O(N)time & O(1)memory ???
for (size_t i = 0; i < image.size(); ++i)
{
for (size_t j = 0; j < (image.size() - i); ++j)
{
swap(image[i][j], image[image.size() - j - 1][image.size() - i - 1]);
}
}
cout << "\n******* rotated image ******" << endl;
for (const auto& i : image)
{
for (const auto& j : i)
{
cout << j << ' ';
}
cout << '\n';
}
}Solution
This code doesn't rotate the image 90 degrees clockwise.
We can see this by making each entry in the matrix distinct (the important part is moving
Then the output is
We can see this by making each entry in the matrix distinct (the important part is moving
value++ inside the inner loop)for (auto& i : image)
{
for (auto& j : i)
{
cout << setfill(' ') << setw(3) << (j = value) << ' ';
value++;
}
cout << '\n';
}Then the output is
$ ./a.exe
******* original image ******
0 1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31 32 33 34
35 36 37 38 39 40 41
42 43 44 45 46 47 48
******* rotated image ******
48 41 34 27 20 13 6
47 40 33 26 19 12 5
46 39 32 25 18 11 4
45 38 31 24 17 10 3
44 37 30 23 16 9 2
43 36 29 22 15 8 1
42 35 28 21 14 7 0Code Snippets
for (auto& i : image)
{
for (auto& j : i)
{
cout << setfill(' ') << setw(3) << (j = value) << ' ';
value++;
}
cout << '\n';
}$ ./a.exe
******* original image ******
0 1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31 32 33 34
35 36 37 38 39 40 41
42 43 44 45 46 47 48
******* rotated image ******
48 41 34 27 20 13 6
47 40 33 26 19 12 5
46 39 32 25 18 11 4
45 38 31 24 17 10 3
44 37 30 23 16 9 2
43 36 29 22 15 8 1
42 35 28 21 14 7 0Context
StackExchange Code Review Q#73990, answer score: 5
Revisions (0)
No revisions yet.