leetcode

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 };