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. OK, I Understand
 
Top