Time: runtime O(1), preprocessing O(nlogn), Memory:O(n), simple solution


  • 0
    V
    class Solution {
      public:
        Solution(vector<int> nums) {
            sorted_nums.resize(nums.size());
            for (int i = 0; i < nums.size(); ++i) {
                sorted_nums[i] = pair<int, int>(nums[i], i);
            }
            sort(sorted_nums.begin(), sorted_nums.end());
    
            int st = -1, len = 0;
            for (int i = 0; i < sorted_nums.size(); ++i) {
                if (!i || sorted_nums[i].first != sorted_nums[i - 1].first) {
                    if (len != 0) {
                        index_map[sorted_nums[i - 1].first] = pair<int, int>(st, len);
                        len = 0;
                    }
                    st = i;
                }
                ++len;
            }
    
            if (len != 0) {
                index_map[sorted_nums[sorted_nums.size() - 1].first] = pair<int, int>(st, len);
            }
        }
    
        int pick(int target) {
            return sorted_nums[index_map[target].first + rand() % index_map[target].second].second;
        }
    
      private:
        // first: number, second: index
        vector<pair<int, int>> sorted_nums;
        // first: start_index, second: length
        unordered_map<int, pair<int, int>> index_map;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.