LeetCode-398 随机数索引
2024-10-21 02:47:48
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/random-pick-index
题目描述
给定一个可能含有重复元素的整数数组,要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意:
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
示例:
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);
解题思路
很明显这个题的场景是数据太大,内存无法全部加载,所以需要想办法压缩数据。
思路有两个:
一个是压缩数据,因为存在重复数据,所以可以合并数据并且记录重复次数,这样初始化时间复杂度为O(n), pick时间复杂度为O(1).
一个是使用数学规律,并不需要加载数据,所以初始化复杂度为O(1),但是在pick的时候记录遇到target的次数cnt,然后取一个[0,cnt)的随机数,如果这个随机数为0 则取这个索引,可以证明每个索引的概率是相同的。
证明:假设有k个target,那么在第cnt次取到索引的概率是
代码展示
哈希表暴力法:
class Solution {
public:
unordered_map<int, vector<int>> m_Nums;
Solution(vector<int>& nums) {
for(int i = 0; i < nums.size(); i++)
{
m_Nums[nums[i]].push_back(i);
}
} int pick(int target) {
int iRand = rand() % m_Nums[target].size();
return m_Nums[target][iRand];
}
}; /**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* int param_1 = obj->pick(target);
*/
水池抽样法:
class Solution {
public:
vector<int> m_Nums;
Solution(vector<int>& nums)
:m_Nums(nums)
{
} int pick(int target) {
int iCnt = 0, iIndex;
for(int i = 0; i < m_Nums.size(); i++)
{
if(target == m_Nums[i])
{
iCnt++;
if(rand() % iCnt == 0)
iIndex = i;
}
}
return iIndex;
}
}; /**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* int param_1 = obj->pick(target);
*/
运行结果
最新文章
- PHP代码优化
- C#封装程序集自定义类方法注释提示
- Ipad Safari iframe cookie 当浏览器默认禁用第三方COOKIE
- MFC中混合使用Duilib制作界面
- CentOS6.3下安装VSFTP服务
- 用时间复杂度为n的方法找出水王
- google protobuf使用
- WCF约束名称的用法
- VirtualBox的工作原理&;参考网上文章
- 为 Date 对象添加 ago 属性
- DevExpress VCL 一键安装工具
- 帝国cms本地搬家到服务器文章路径问题?
- MongoDB 学习笔记(原创)
- LinkedBlockingQueue简介
- python3 练手实例4 九九乘法口诀表
- bzoj 2527: [Poi2011]Meteors
- ASP.NET中Page_Load()与Page_Init()的区别
- 第 4 章 容器 - 028 - 限制容器对CPU的使用
- JS 原型链 prototypt 和隐式原型 _proto_
- AVL树与红黑树(R-B树)的区别与联系
热门文章
- Spring IOC源码(二):IOC容器之 刷新前的准备
- 更改jenkins插件地址为国内源地址
- Flask 终端启动运行
- 后端流传输excel文件到前端
- Hadoop详解(03)-Hadoop编译源码-了解
- 为什么要虚拟化,为什么要容器,为什么要Docker,为什么要K8S?
- 浏览器刷新时候不删除信息,关闭后删除用户信息处理办法,浏览器监听刷新以及删除事件、cookie、session、sessionStorage、localStorage区别
- DVWA靶场实战(十一)——XSS(Reflected)
- 注解_概念-注解_JDK内置注解
- 10月28日内容总结——ATM项目开发流程