SHARE
TWEET

Untitled

bbescos Jan 20th, 2019 58 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. #include <unordered_map>
  7. #include <numeric>
  8.  
  9. using namespace std;
  10.  
  11. //Runtime complexity O(n^2)
  12. //Memory complexity O(1)
  13. int singleNumber(const vector<int>& nums) {
  14.     for (int num: nums){
  15.         int times = std::count(nums.begin(), nums.end(), num); //count in vectors is O(n)
  16.         if (times == 1)
  17.             return num;
  18.     }
  19.     return -1;
  20. }
  21.  
  22. //Runtime complexity O(nlogn)
  23. //Memory complexity O(1)
  24. int singleNumber_2(vector<int>& nums) {
  25.     sort(nums.begin(), nums.end()); //O(nlogn)
  26.     if (nums[0] != nums[1])
  27.         return nums[0];
  28.    
  29.     if (nums[nums.size() - 1] != nums[nums.size() - 2])
  30.         return nums[nums.size() - 1];
  31.    
  32.     for (int i = 1; i < nums.size() - 1; ++i){
  33.         if (nums[i] != nums[i-1] && nums[i] != nums[i+1])
  34.             return nums[i];
  35.     }
  36.     return -1;
  37. }
  38.  
  39. //Runtime complexity O(n)
  40. //Memory complexity O(n)
  41. // hashmap[nums[i]]
  42. // if hashmap does not contain the key nums[i] -> it creates it and returns a reference to the value, which is init to 0;
  43. // if it contains the key -> it returns a reference to the value;
  44. int singleNumber_3(const vector<int>& nums) {
  45.     unordered_map<int, int> hashmap;
  46.     for (int i = 0; i < nums.size(); ++i)
  47.         ++hashmap[nums[i]];
  48.    
  49.     for (auto& i: hashmap)
  50.         if (i.second == 1)
  51.             return i.first;
  52.    
  53.     return -1;
  54. }
  55.    
  56. // Runtime complexity O(n)
  57. // Memory complexity O(1)
  58. // 7 3 7 3 1
  59. // 0 ^ 7 ^ 3 ^ 7 ^ 3 ^ 1
  60. // 0 ^ (3 ^ 3) ^ (7 ^ 7) ^ 1
  61. // 0 ^ 0 ^ 0 ^ 1
  62. // 1
  63. // 0 ^ 7 = 7
  64. // 7 ^ 3 = 111 ^ 011 = 100 = 4
  65. int singleNumber_4(const vector<int>& nums) {
  66.     int result = 0;
  67.     for (int num: nums){
  68.         result = result ^ num;
  69.     }
  70.     return result;
  71. }
  72.  
  73. int xor(int acc, int new_n) {
  74.     return acc^new_n;
  75. }
  76.  
  77. int singleNumber_5(const vector<int>& nums) {
  78.     return accumulate(nums.begin(), nums.end(), 0, [](int x, int y) { return x^y;});
  79. }
  80.  
  81. void print_vector(const vector<int>& vector) {
  82.     for (auto& i : vector) { // const, auto, & || const-> no se pueda modificar | auto = vector<int> | & = ref
  83.         cout << i << " ";
  84.     }
  85. }
  86.  
  87. int main(){
  88.    
  89.     vector<int> trial1 = {1,2,1,2,4};
  90.     vector<int> trial2 = {1,2,4,2,4};
  91.     vector<int> trial3 = {1,2,1,4,4};
  92.    
  93.     int result1 = singleNumber_4(trial1);
  94.     int result2 = singleNumber_4(trial2);
  95.     int result3 = singleNumber_4(trial3);
  96.    
  97.     int expected1 = 4;
  98.     int expected2 = 1;
  99.     int expected3 = 2;
  100.    
  101.     vector<vector<int>> trials = {trial1, trial2, trial3};
  102.     vector<int> results = {result1, result2, result3};
  103.     vector<int> expecteds = {expected1, expected2, expected3};
  104.    
  105.     for (int i = 0; i < trials.size(); ++i) {
  106.         cout << " ----  TRIAL " << i + 1 << ". ------" << endl;
  107.         cout << "Vector: ";
  108.         print_vector(trials[i]);
  109.         cout << endl << "Expected result: "<< expecteds[i]<<". Obtained result: "<<results[i]<<endl;
  110.        
  111.     }
  112.    
  113.    
  114.     return 0;
  115. }
  116.  
  117. //
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