SHARE
TWEET

Untitled

bbescos Jan 20th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Runtime complexity O(n^2)
  2. //Memory complexity O(1)
  3. int singleNumber(vector<int>& nums) {
  4.     for (int num: nums){
  5.         int times = std::count(nums.begin(), nums.end(), num); //count in vectors is O(n)
  6.         if (times == 1) {return num;}
  7.     }
  8.     return -1;
  9. }
  10.  
  11. //Runtime complexity O(nlogn)
  12. //Memory complexity O(1)
  13. int singleNumber(vector<int>& nums) {
  14.     sort(nums.begin(), nums.end());
  15.     if (nums[0] != nums[1]) return nums[0];
  16.     if (nums[size(nums) - 1] != nums[size(nums) - 2]) return nums[size(nums) - 1];
  17.     for (int i = 1; i < size(nums) - 1; ++i){
  18.         if (nums[i] != nums[i-1] && nums[i] != nums[i+1]) return nums[i];}
  19.         return -1;
  20.     }
  21.  
  22. //Runtime complexity O(n)
  23. //Memory complexity O(n)
  24. int singleNumber(vector<int>& nums) {
  25.     unordered_map<int, int> hashmap;
  26.     for (int i = 0; i < size(nums); ++i){
  27.         if (hashmap.count(nums[i]) == 0) hashmap[nums[i]] = 1;
  28.         else hashmap[nums[i]] = 2;
  29.     }
  30.     for (auto i: hashmap){
  31.         if (i.second == 1) return i.first;
  32.     }
  33.    
  34.     return -1;
  35. }
  36.    
  37. //Runtime complexity O(n)
  38. //Memory complexity O(1)
  39. int singleNumber(vector<int>& nums) {
  40.     int result = 0;
  41.     for (int num: nums){
  42.         result = result ^ num;
  43.     }
  44.    
  45.     return result;
  46. }
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