• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top