【刷题日记】398. 随机数索引

本次刷题日记的第 43 篇，力扣题为：398. 随机数索引 ，中等

一、题目描述：

今天的题目还不太一样，又是一个需要我们完成小需求的题目，而不是完成一个简单的算法，没有关系，不就是 2 个函数吗，相信很快就能搞定，完成后加个鸡腿

二、这道题考察了什么思想？你的思路是什么？

来仔细过一下这个题给到我们的重点信息有哪些？

• 题目中给出咱们的一个数组，数组中全部都是整数，这里面会出现多个重复的数字
• 题目要求输入是某个数字的时候，我们可以输出这个数字在数组中的随机一个索引

其实看到这个需求，这个不像是一个中等题，应该是一个简单题才对，因为看到题的时候，思路很明确，实现方式脑海中也是很明确的，形式非常明朗

我们可以一起来分析一下这个题，题目中需要我们找到一个重复数字的随机索引，那么我们必须得知道需要在哪个范围里面进行随机

要明确找到一个范围来进行随机，那么就需要知道每一个数字对应的范围是多少，进而其实就很容易想到用一个 hash 表来进行处理了

我们可以这样：

看到这个 hash 表，我们就知道对应的字符串应该是这个样子的：131136666555

那么按照题目中给出的示例，对应的 hash 表就是这个样子的

如上图，有了这个 hash 表之后，当 Pick 函数给出的 数字是 3，那么我们就可以很容易的找到对应的数组是 [2,3,4] ，那么取一个随机值就是一个很简单的事情了

现在我们就可以按照这个思路来进行编码了

• 初始化 hash 表， hash 表的结构， key 是 数字，值是一个切片，元素是数字

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，此处需要注意，咱们的 hash 表 key 是一个字符串，值是一个切片，这个切片主要是用来存放对应数字的所有索引记录的，便于 pick 函数进行处理

// 定义好 map[int][]int 结构 
type Solution map[int][]int
func Constructor(nums []int) Solution {
    helper := map[int][]int{}
    // 遍历题目给出的数组，初始化 hash 表
    for i, v := range nums {
        helper[v] = append(helper[v], i)
    }
    return helper
}
func (helper Solution) Pick(target int) int {
    inSlice := helper[target]
    // 查询 hash 表，key 对应的数组，数组中取随机值
    return inSlice[rand.Intn(len(inSlice))]
}
/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.Pick(target);
 */

按照这种方式来进行编码，效果很明显，思路很清晰，写起来也很容易，其实就是一个 hash 表的简单应用

四、总结：

就按照这种编码实现方式，时间复杂度是多少呢？

我们这里涉及到两个函数，那么肯定是要分别来计算的咯

时间复杂度，初始化 hash 表的时候，时间复杂度是 O(n) ，Pick 函数获取随机索引的时间复杂度是 O(1) ，咱们是直接通过 hash 表的 key 来获取值

那么空间复杂度是不是就很明确了，整体的空间复杂度是 O(n)， 因为我们引入了一个 hash 表的消耗 ，hash 表的长度为 n ，则空间复杂度是 O(n)

原题地址：398. 随机数索引

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~