- Question
- Ideas
- 1、Answer( Java )
- `⚡️ getOrDefault(Object key, V defaultValue)`
- Code①( HashMap 实现)
- Code②( ArrayList 实现)
- 2、Answer( Java )
- Code( 蓄水池抽样 )
398. 随机数索引
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/random-pick-index/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Ideas 1、Answer( Java )
解法思路:哈希表预处理
⚡️ getOrDefault(Object key, V defaultValue)
获取指定 key
对应对 value
,如果找不到 key
,则返回设置的默认值。
👍使用哈希表以 nums[i]
为键,下标集合 List
作为值进行存储。( ArrayList
同理)
/**
* @author Listen 1024
* @description 398. 随机数索引(哈希表预处理 Or 蓄水池抽样)
* @date 2022-04-25 10:50
*/
class Solution {
Random random = new Random();
Map<Integer, List<Integer>> map = new HashMap<>();
public Solution(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
List<Integer> list = map.getOrDefault(nums[i], new ArrayList<Integer>());
list.add(i);
map.put(nums[i], list);
}
}
public int pick(int target) {
int res = 0;
List<Integer> list = map.get(target);
int i = random.nextInt(list.size());
res = list.get(i);
return res;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int param_1 = obj.pick(target);
*/
Code②( ArrayList 实现)
/**
* @author Listen 1024
* @description 398. 随机数索引(哈希表预处理 Or 蓄水池抽样)
* @date 2022-04-25 10:50
*/
class Solution {
ArrayList<Integer> list = new ArrayList<>();
public Solution(int[] nums) {
for (int num : nums) {
list.add(num);
}
}
public int pick(int target) {
int res = 0;
ArrayList<Integer> cnt = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == target) {
cnt.add(i);
}
}
Random random = new Random();
int i = random.nextInt(cnt.size());
res = cnt.get(i);
return res;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int param_1 = obj.pick(target);
*/
2、Answer( Java )
解法思路:蓄水池抽样
👍规定当遇到第 k
个满足 nums[i]=target
的下标时,执行一次 [0, k)
的随机 *** 作,当随机结果为 0
时( 发生概率为 1/k
),我们将该坐标作为最新的答案候选。
/**
* @author Listen 1024
* @description 398. 随机数索引(哈希表预处理 Or 蓄水池抽样)
* @date 2022-04-25 10:50
*/
class Solution {
Random random = new Random();
int[] _nums;
public Solution(int[] nums) {
_nums = nums;
}
public int pick(int target) {
int index = 0, cnt = 0;
int len = _nums.length;
for (int i = 0; i < len; i++) {
if (_nums[i] == target) {
cnt++;
if (random.nextInt(cnt) == 0) {
index = i;
}
}
}
return index;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int param_1 = obj.pick(target);
*/
题解二参考链接
https://leetcode-cn.com/problems/random-pick-index/solution/by-ac_oier-zhml/
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)