SHARE
TWEET

Untitled

bbescos Jan 20th, 2019 61 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. //Run-time complexity O(n*k)
  10. //Memory complexity O(1)
  11. // 0 1 2 3 4 k = 0
  12. // 4 0 1 2 3 k = 1
  13. // 3 4 0 1 2 k = 2
  14. // 2 3 4 0 1 k = 3
  15. // 0 1 2 3 4 k = 4
  16. // 4 0 1 2 3 k = 5
  17.  
  18. //Run-time complexity O(n * min(n,k)) --> at most O(n^2)
  19. void rotate(vector<int>& nums, int k) {
  20.     k = k % nums.size();
  21.     for (int i = 0; i < k; ++i){
  22.         nums.insert(nums.begin(), nums[nums.size() - 1]); //O(n)
  23.         nums.pop_back(); //O(1)
  24.     }
  25. }
  26.  
  27. // Rotate 2
  28. // {0, 1, 2, 3, 4, 5}
  29. // {4, 5, 0, 1, 2, 3} --- 2 vectors {4, 5}, {0, 1, 2, 3}
  30. // Memory complexity O(n)
  31. // Run-time complexity O(n)
  32. void rotate_2(vector<int>& nums, int k) {
  33.     k = k % nums.size();
  34.     vector<int> first_vector(nums.begin(), nums.end() - k);
  35.     vector<int> second_vector(nums.end() - k, nums.end());
  36.    
  37.     second_vector.insert(second_vector.end(), first_vector.begin(), first_vector.end()); // O(n_f)
  38.    
  39.     nums = second_vector;
  40. }
  41.  
  42. // 1 2 3 4 5 k = 2
  43. // 5 4 3 2 1
  44. // 4 5 3 2 1
  45. // 4 5 1 2 3
  46. // Memory complexity O(1)
  47. // Run-time complexity O(n)
  48. void rotate_3(vector<int>& nums, int k) {
  49.     if (k <= 0)
  50.         return;
  51.    
  52.     k = k % nums.size();
  53.     reverse(nums.begin(), nums.end());
  54.     reverse(nums.begin(), nums.begin() + k);
  55.     reverse(nums.begin() + k, nums.end());
  56. }
  57.  
  58. void print_vector(const vector<int>& vector) {
  59.     for (auto& i : vector) { // const, auto, & || const-> no se pueda modificar | auto = vector<int> | & = ref
  60.         cout << i << " ";
  61.     }
  62. }
  63.  
  64. int main(){
  65.    
  66.     vector<int> vec_1 = {1, 2, 3, 4, 5};
  67.     int k1 = 0;
  68.     vector<int> expected_1 = {1, 2, 3, 4, 5};
  69.    
  70.     vector<int> vec_2 = {1, 2, 3, 4, 5, 6};
  71.     int k2 = 3;
  72.     vector<int> expected_2 = {4, 5, 6, 1, 2, 3};
  73.    
  74.     vector<int> vec_3 = {1, 2, 3, 4, 5};
  75.     int k3 = 100;
  76.     vector<int> expected_3 = {1, 2, 3, 4, 5};
  77.  
  78.     vector<int> vec_4 = {1, 2, 3, 4, 5};
  79.     int k4 = 3;
  80.     vector<int> expected_4 = {3, 4, 5, 1, 2};
  81.  
  82.     vector<int> vec_5 = {1, 2, 3, 4, 5};
  83.     int k5 = 8;
  84.     vector<int> expected_5 = {3, 4, 5, 1, 2};
  85.  
  86.    
  87.     vector<vector<int>> expecteds = {expected_1, expected_2, expected_3, expected_4, expected_5};
  88.     vector<vector<int>> vecs = {vec_1, vec_2, vec_3, vec_4, vec_5};
  89.     vector<int> ks = {k1, k2, k3, k4, k5};
  90.    
  91.     for (int i = 0; i < expecteds.size(); ++i) {
  92.         cout<<" ------- TEST "<<i+1<<" -------"<<endl;
  93.         cout<<"Expected: ";
  94.         print_vector(expecteds[i]);
  95.         cout<<endl<<"Obtained: ";
  96.         rotate_3(vecs[i], ks[i]);
  97.         print_vector(vecs[i]);
  98.         cout<<endl;
  99.                      
  100.     }
  101.    
  102.     return 0;
  103. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top