1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
private Map<Integer, List<Integer>> numIdxMap;
private Random rand;
public Solution(int[] nums) {
numIdxMap = new HashMap<>();
rand = new Random();
for (int i = 0; i < nums.length; i++) {
numIdxMap.putIfAbsent(nums[i], new ArrayList<>());
numIdxMap.get(nums[i]).add(i);
}
}
public int pick(int target) {
List<Integer> targetIdxList = numIdxMap.get(target);
return targetIdxList.get(rand.nextInt(targetIdxList.size()));
}
}
|
最直接的, 用map来存每个元素以及它们都在哪些index出现了.
等到需要pick的时候, 随机生成该元素从0到出现次数(exclusive)范围内的数字, 然后去map中该元素对应存该元素出现在哪些index的list中去访问以这个随机生成的数字为index的元素值. 感觉描述有些多余. 直接看代码吧.
时间复杂度: 初始化是O(N), pick是O(1)
空间复杂度: O(n) 用了map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
private int[] nums;
private Random rand;
public Solution(int[] nums) {
this.nums = nums;
rand = new Random();
}
public int pick(int target) {
int count = 0, result = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
count += 1;
if (rand.nextInt(count) == 0) {
result = i;
}
}
}
return result;
}
}
|
这个叫reservoir sampling. 这个解法会超时, 算是学习一下新的东西. 假设我们要pick一个数字, 这个数字有n个duplicates. 那么我们假设要挑到第m个(1-index), 那概率是多少? 按照我们的逻辑, 当我们count到第m个的时候, 我们让count + 1. 此时count == m. 那么如果要摇到第m个, 此时就需要让rand产生0. 此时概率为1 / m因为范围是[0, m). 然后我们遇到第m + 1个duplicates的时候, count继续加1变为m + 1. 如果我们要保留之前摇到的m, 我们就需要让此时摇到初0之外的数字, 这样上一次摇的的m就得以保留. 那么此时这样的概率就是(1 / m) * (m / m + 1). 第一项是上一次摇到m的概率乘上现在不摇到0个概率, 于是是1/ m + 1. 以后也是一样的道理来推. 这样m可以适用于任何位置上的duplicate. 思路大概就是这样的.
时间复杂度: 初始化O(1). pick是O(n)
空间复杂度: O(1) 如果不算传进来的输入的话
