本文已参加「新人创造礼」活动，一同开启创造之路。

随机数索引（一题双解）【Leetcode每日（4.25）一题】C++

前语

今日的每日一题的质量蛮高的，咱们能够有时刻优先和空间优先的两种角度去思考解题并优化算法和代码。

本题来自398. 随机数索引 – 力扣（LeetCode） (leetcode-cn.com)

题目描绘

给定一个或许含有重复元素的整数数组，要求随机输出给定的数字的索引。 您能够假定给定的数字一定存在于数组中。

注意：
数组大小或许非常大。 运用太多额定空间的解决方案将不会经过测试。

示例

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) 应该回来索引 2,3 或者 4。每个索引的回来概率应该持平。
solution.pick(3);
// pick(1) 应该回来 0。因为只要nums[0]等于1。
solution.pick(1);

以下是题解：

哈希表——空间换时刻

首先咱们不难想出用空间换时刻的思路，运用键值对 比方哈希表的数据结构，以数值为键，下标为值存储。而值能够采用可变数组vector存储。

所以咱们能够在创立类目标的时分建立哈希表，然后在pick函数中随机回来值对应的下标。

这样的好处在于，置需求遍历一遍数组，将数组存入哈希表，然调用pick函数直接回来即可，时刻复杂度O(n)， 空间复杂度O(n)。

以下是C++代码

Code（C++）

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
class Solution 
{
private:
    // 一个哈希表， 用来存储相同值对应的下标索引
    unordered_map<int, vector<int>> indexs;
public:
    /// <summary>
    /// 在类目标结构时遍历完成下标哈希表的建立
    /// </summary>
    /// <param name="nums"></param>
    Solution(vector<int>& nums) 
    {
        for (int i = 0; i < nums.size(); ++i)
        {
            // 存储同值下标
            indexs[nums[i]].push_back(i);
        }
    }
    /// <summary>
    /// 调用哈希表和随机函数来获取哈希表
    /// </summary>
    /// <param name="target"></param>
    /// <returns></returns>
    int pick(int target) 
    {
        int size = indexs[target].size();
        vector<int>& index = indexs[target];
        // 回来随机索引
        return index[rand() % size];
    }
};
/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * int param_1 = obj->pick(target);
 */
int main(int argc, char** argv)
{
    int n;
    while (cin >> n)
    {
        vector<int> nums(n);
        for (int& num : nums)
        {
            cin >> num;
        }
        Solution* obj = new Solution(nums);
        int op;         // 指令参数，0——完毕，1——持续，即pick指令
        cin >> op;
        while (op > 0)
        {
            int target;
            cin >> target;
            int param_1 = obj->pick(target);    // 调用pick函数，得到随机下标索引
            cout << param_1 << endl;
            cin >> op;
        }
    }
	return 0;
}

概率论，不放回抽样——时刻换空间

欸，假如咱们从空间优先的角度出发，会怎么样呢？

咱们不难发现，假如不运用额定的空间，那咱们在调用pick函数的时分，显然至少需求遍历数组的，并且咱们需求在找到数值时，随机判别是否回来。

欸？这个模式，大家是否有点了解，没错，这便是咱们在概率论常遇到不放回抽样问题，无妨假定数组中要找到的值有n个，那么关于找到的第一个的下标，其概率有

以此类推，不难发现每一个下标回来的概率都是 1/ n。

所以咱们能够在每次pick函数调用中，先遍历数组，假如找到元素时，就 rand()%n, 假如得到0，欸，问题又来了，在遍历的时分，咱们又不知道有多少个同值数组。其实也很简单，咱们能够在遍历的时分记载数量，咱们只需求考虑当时的数量然后得到随机值，咱们置需求记载最后一次随机为0的下标即可，比方

思路清晰了，咱们就来上代码吧

Code（C++）

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
class Solution 
{
private:
    vector<int>& nums;
public:
    /// <summary>
    /// 引用目标
    /// </summary>
    /// <param name="nums"></param>
    Solution(vector<int>& nums) : nums(nums)  // 引用目标，其实不占用空间
    {}
    /// <summary>
    /// 遍历数组
    /// </summary>
    /// <param name="target"></param>
    /// <returns></returns>
    int pick(int target) 
    {
        int cnt = 0;        // 当时找到的target的数量
        int ans = -1;       // 初始化答案
        // 遍历数组
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] == target)  // 找到数值
            {
                cnt++;  // 数量+1
                if (rand() % cnt == 0)  // 更新答案
                {
                    ans = i;
                }
            }
        }
        return ans;
    }
};
/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * int param_1 = obj->pick(target);
 */
int main(int argc, char** argv)
{
    int n;
    while (cin >> n)
    {
        vector<int> nums(n);
        for (int& num : nums)
        {
            cin >> num;
        }
        Solution* obj = new Solution(nums);
        int op;         // 指令参数，0——完毕，1——持续，即pick指令
        cin >> op;
        while (op > 0)
        {
            int target;
            cin >> target;
            int param_1 = obj->pick(target);    // 调用pick函数，得到随机下标索引
            cout << param_1 << endl;
            cin >> op;
        }
    }
	return 0;
}

后话

持续加油！