• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

bbescos Jan 20th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. // Compiled with: g++ -Wall -std=c++14 -pthread
2.
3. #include <iostream>
4. #include <vector>
5. #include <algorithm>
6.
7. using namespace std;
8.
9. //This is NOT an in-place algorithm
10. //x' = x*cos(a) - y*sin(b)
11. //y' = x*sin(a) + y*cos(b)
12. //With this we rotate around the center of the matrix
13. //If matrix is n x n. Memory Complexity O(n^2)
14. //Runtime Complexity O(n^2)
15. void rotate(vector<vector<int>>& matrix) {
16.     // Copia
17.     vector<vector<int>> _matrix = matrix;
18.     for (int i = 0; i < matrix.size(); ++i){
19.         for (int j = 0; j < matrix.size(); ++j){
20.             matrix[i][j] = _matrix[matrix.size() - 1 - j][i];
21.         }
22.     }
23. }
24.
25.
26. //This is an in-place algorithm
27. //If matrix is n x n. Memory Complexity O(1)
28. //Runtime Complexity O(n^2)
29. //This is faster because the second for loop iterates as maximum n/2.
30. void rotate_2(vector<vector<int>>& matrix) {
31.
32.     // swap -> 1 variable extra y 2 assignments
33.     // 3 swaps -> 6 cambios (9)
34.     // ---------> 4 + 1 temp (5)
35.     //
36.     int n = matrix.size();
37.     for (int i = 0; i < n; ++i){
38.         for (int j = i + 1; j < n - i; ++j){
39.             // aqui ya se donde tiene que ir cada uno de estos 4 numeros
40.             // (i,j), (j, n-1-i), (n-1-i, n-1-j), (n-1-j, i)
41.             // 3 swaps
42.             // int temp = matrix[i][j];
43.             // matrix[i][j] = matrix[n - 1 - j][i];
44.             // matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
45.             // matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
46.             // matrix[j][n - 1 - i] = temp;
47.             swap(matrix[i][j], matrix[j][n - 1 - i]);
48.             swap(matrix[i][j], matrix[n - 1 - i][n - 1 - j]);
49.             swap(matrix[i][j], matrix[n - 1 - j][i]);
50.         }
51.     }
52. }
53.
54.
55. //This is an in-place algorithm
56. //If matrix is n x n. Memory Complexity O(1)
57. //Runtime Complexity O(n^2)
58. void rotate_flipao(vector<vector<int>>& matrix) {
59.     int n = matrix.size();
60.     for (int i = 0; i < n; ++i){
61.         for (int j = i + 1; j < n; ++j){
62.             swap(matrix[i][j], matrix[j][i]);
63.         }
64.     }
65.
66.     for (int i = 0; i < n; ++i){
67.         reverse(matrix[i].begin(), matrix[i].end()); //O(n)
68.     }
69. }
70.
71. void print_matrix(const vector<vector<int>>& matrix) {
72.     for (auto& row : matrix) { // const, auto, & || const-> no se pueda modificar | auto = vector<int> | & = ref
73.         for (auto i : row) {
74.             cout << i << " ";
75.         }
76.         cout << endl;
77.     }
78. }
79.
80. int main(){
81.
82.     vector<vector<int>> matrix_1 =
83.     {{1, 2, 3, 4},
84.     {5, 6, 7, 8},
85.     {9, 10, 11, 12},
86.     {13, 14, 15, 16}};
87.
88.     vector<vector<int>> matrix_2 =
89.     {{1, 2, 3, 4, 101},
90.     {5, 6, 7, 8, 102},
91.     {9, 10, 11, 12, 103},
92.     {13, 14, 15, 16, 104},
93.     {17, 18, 19, 20, 105}};
94.
95.     cout<<"---Test 1 ----"<<endl;
96.     cout<<"Original matrix:"<<endl;
97.     print_matrix(matrix_1);
98.     cout<<"Rotated matrix:"<<endl;
99.     rotate_2(matrix_1);
100.     print_matrix(matrix_1);
101.
102.     cout<<endl<<"---Test 2 ----"<<endl;
103.     cout<<"Original matrix:"<<endl;
104.     print_matrix(matrix_2);
105.     cout<<"Rotated matrix:"<<endl;
106.     rotate_2(matrix_2);
107.     print_matrix(matrix_2);
108.
109.     return 0;
110. }
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.
Not a member of Pastebin yet?