• API
• FAQ
• Tools
• Archive
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.

Top