+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-08(62)

2019-09(107)

2019-10(19)

2019-11(7)

2019-12(18)

leetcode 398. Random Pick Index(python)

发布于2021-01-15 21:02     阅读(771)     评论(0)     点赞(10)     收藏(5)


0

1

2

3

4

描述

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.

Example 1:

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);

Note:

The array size can be very large. Solution that uses too much extra space will not pass the judge.

解析

根据题意,给出了一个列表 nums ,只要用字典 d 记录下每个元素及其对应的所有出现过的索引组成的列表,然后通过一个随机数从 d[target] 中提取一个索引即可。

解答

class Solution(object):
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.d = {}
        for i, v in enumerate(nums):
            if v in self.d:
                self.d[v].append(i)
            else:
                self.d[v] = [i]

    def pick(self, target):
        """
        :type target: int
        :rtype: int
        """
        arr = self.d[target]
        return arr[random.randint(0, len(arr) - 1)]

运行结果

Runtime: 288 ms, faster than 44.99% of Python online submissions for Random Pick Index.
Memory Usage: 22.9 MB, less than 34.15% of Python online submissions for Random Pick Index.

解析

根据题意,找出 target 在 nums 中出现过的索引列表,然后随机选择一个返回即可。

解答

class Solution(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums

    def pick(self, target):
        """
        :type target: int
        :rtype: int
        """
        idxs = [i for i,num in enumerate(self.nums) if num==target]
        return random.choice(idxs)

运行结果

Runtime: 236 ms, faster than 96.48% of Python online submissions for Random Pick Index.
Memory Usage: 17 MB, less than 91.60% of Python online submissions for Random Pick Index.

解析

根据题意,遍历 nums ,找出第一次出现 target 的位置索引即可,此种解法不知道为何会报错,可能是因为结果没有随机性吧。

解答

class Solution(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums


    def pick(self, target):
        """
        :type target: int
        :rtype: int
        """
        for i,num in enumerate(self.nums):
            if num!=target:
                continue
            else:
                return i

运行结果

Wrong 

原题链接:https://leetcode.com/problems/random-pick-index/

原文链接:https://blog.csdn.net/wang7075202/article/details/112630281

0

1

2

3

4

5

6

7

8

9



所属网站分类: 技术文章 > 博客

作者:坚持才能胜利

链接: https://www.pythonheidong.com/blog/article/771943/3cffb9a5c03b8e361dc3/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

10 0
收藏该文
已收藏

评论内容:(最多支持255个字符)