leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0398.cpp (818B)

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