Linked List Random Node
Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.
Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
这道题如果不考虑follow up会很简单，遍历一遍链表，把值存到一个List里，取的时候随机出一个下标来取就好。
public class Solution {
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
private ArrayList<Integer> a=new ArrayList<Integer>();
private int b = 0;
public Solution(ListNode head) {
while (head!=null) {
a.add(head.val);
head = head.next;
b++;
}
}
/** Returns a random node's value. */
public int getRandom() {
int index = (int)(Math.random()*(b));
int res = a.get(index);
return res;
}
}
但是，如果在长度未知的情况下进行随机，这个就不行了，比如链表是随时变化的，就不能用这样的方法。
这是著名的蓄水池问题，在未知长度的数据中随机出k个数据。
比如，我们要从1，2，3中随机选出一个。
假设我们的结果是res
我们从头开始遍历这个链表：
遍历到第一个时，我们选1的概率是1，res=1
遍历到第二个时，我们选2的概率应该是1/2，1的概率也应该是是1/2。我们以1/2的概率执行res＝2
遍历到第三个时，我们选每个数的概率是1/3，我们以1/3的概率执行res＝3
此时，res＝1，2，3的概率分别是1/2(1-1/3),1/2(1-1/3),1/3。即1/3，1/3，1/3
所以：
public class Solution {
ListNode head;
Random random;
public Solution(ListNode head) {
this.head = head;
random = new Random();
}
/** Returns a random node's value. */
public int getRandom() {
int count = 0;
int result = -1;
ListNode dummyhead = head;
while(dummyhead != null) {
if(random.nextInt(++count) == 0) {
result = dummyhead.val;
}
dummyhead = dummyhead.next;
}
return result;
}
}
Random Pick Index
Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.
Note:The array size can be very large. Solution that uses too much extra space will not pass the judge.
Example:
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);
// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);
这个和上面的问题几乎一样的，就是这次选的时候只在特定的值中选
public class Solution {
int [] data;
Random random;
public Solution(int[] nums) {
data = nums;
random = new Random();
}
public int pick(int target) {
int count = 0;
int result = -1;
for(int i = 0;i<data.length;i++) {
if (data[i]==target) {
if(random.nextInt(++count) == 0) {
result = i;
}
}
}
return result;
}
}
