首页 > 代码库 > LeetCode: Linked List Random Node
LeetCode: Linked List Random Node
这题参照http://blog.jobbole.com/42550/
用的蓄水池算法,即更改ans的概率为1/(当前length)
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution { 10 11 private ListNode head; 12 /** @param head The linked list‘s head. 13 Note that the head is guaranteed to be not null, so it contains at least one node. */ 14 public Solution(ListNode head) { 15 this.head = head; 16 } 17 18 /** Returns a random node‘s value. */ 19 public int getRandom() { 20 ListNode p = head; 21 int ans = p.val; 22 for (int i = 1; p.next != null; i++) { 23 p = p.next; 24 if ((int)(Math.random() * (i + 1)) == i) 25 ans = p.val; 26 } 27 return ans; 28 } 29 } 30 31 /** 32 * Your Solution object will be instantiated and called as such: 33 * Solution obj = new Solution(head); 34 * int param_1 = obj.getRandom(); 35 */
LeetCode: Linked List Random Node
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。