本文共 696 字,大约阅读时间需要 2 分钟。
在乱序数组中找到target的随机index,target可能重复。
时间复杂度:O(N),空间复杂度:O(1)
public class Solution { int[] nums; Random random; public Solution(int[] nums) { this.nums = nums; this.random = new Random(); } public int pick(int target) { int count = 1; int res = -1; for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { if (random.nextInt(count) == count - 1) { res = i; } count++; } } return res; }}/** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(nums); * int param_1 = obj.pick(target); */
转载地址:http://mahld.baihongyu.com/