• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled bbescos  Jan 20th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //This is NOT an in-place algorithm
2. //x' = x*cos(a) - y*sin(b)
3. //y' = x*sin(a) + y*cos(b)
4. //With this we rotate around the center of the matrix
5. //If matrix is n x n. Memory Complexity O(n^2)
6. //Runtime Complexity O(n^2)
7. void rotate(vector<vector<int>>& matrix) {
8.     vector<vector<int>> _matrix = matrix;
9.     for (int i = 0; i < size(matrix); ++i){
10.         for (int j = 0; j < size(matrix); ++j){
11.             matrix[i][j] = _matrix[size(matrix) - 1 - j][i];
12.         }
13.     }
14. }
15.
16. //This is an in-place algorithm
17. //If matrix is n x n. Memory Complexity O(1)
18. //Runtime Complexity O(n^2)
19. //This is faster because the second for loop iterates as maximum n/2.
20. void rotate(vector<vector<int>>& matrix) {
21.     int n = size(matrix);
22.     for (int i = 0; i < n; ++i){
23.         for (int j = i + 1; j < n - i; ++j){
24.             swap(matrix[i][j], matrix[j][n - 1 - i]);
25.             swap(matrix[i][j], matrix[n - 1 - i][n - 1 - j]);
26.             swap(matrix[i][j], matrix[n - 1 - j][i]);
27.         }
28.     }
29. }
30.
31. //This is an in-place algorithm
32. //If matrix is n x n. Memory Complexity O(1)
33. //Runtime Complexity O(n^2)
34. void rotate(vector<vector<int>>& matrix) {
35.     int n = size(matrix);
36.     for (int i = 0; i < n; ++i){
37.         for (int j = i + 1; j < n; ++j){
38.             swap(matrix[i][j], matrix[j][i]);
39.         }
40.     }
41.
42.     for (int i = 0; i < n; ++i){
43.         reverse(matrix[i].begin(), matrix[i].end()); //O(n)
44.     }
45. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top