leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0398.cpp (818B)

0 #pragma GCC optimize("fast") 1 static auto _ = []() { 2 ios_base::sync_with_stdio(false); 3 cin.tie(NULL), cout.tie(NULL); 4 return 0; 5 }(); 6 7 // O(n) pick, O(1) space 8 class Solution { 9 const vector<int> &nums; 10 11 public: 12 Solution(const vector<int> &nums) : nums(nums) {} 13 14 int pick(int target) { 15 int n = 0, ans = -1; 16 for (int i = 0; i < nums.size(); i++) { 17 if (nums[i] != target) continue; 18 if (rand() % ++n == 0) ans = i; 19 } 20 return ans; 21 } 22 }; 23 24 // O(1) pick, O(n) space 25 class Solution { 26 unordered_map<int, vector<int>> um; 27 28 public: 29 Solution(const vector<int> &nums) { 30 for (int i = 0; i < nums.size(); i++) 31 um[nums[i]].push_back(i); 32 } 33 34 int pick(int target) { return um[target][rand() % um[target].size()]; } 35 };