Leetcode 398. 随机数索引 C++_Want!的博客-程序员宅基地

Leetcode 398. 随机数索引

题目

给定一个可能含有重复元素的整数数组,要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

注意:

数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例:

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

题解

我们用一个数组存储所有数,然后查找时,第一次查找到,我们令答案等于下标;之后再查找到,我们生成一个随机数,如果能整除这个数当前重复次数,则进行替换。详细过程见代码

代码

class Solution {
    
public:
    vector<int>& nums;
    Solution(vector<int>& nums):nums(nums) {
    
        
    }
    
    int pick(int target) {
    
        int n = nums.size();
        int cnt=0;
        int choice;
        for(int i=0; i<n; i++){
    
            if(nums[i] == target){
    
                cnt++;
                if(cnt == 1)    choice = i;
                else if(rand() % cnt == 0)  choice = i;
            }
        }
        return choice;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * int param_1 = obj->pick(target);
 */

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/random-pick-index
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43750513/article/details/107129422

智能推荐

cas后端返回html直接跳转,Cas登录服务端退出不提供跳转到登录解决_舒允个人提升的博客-程序员宅基地

1、由于使用单点登录时服务端只提供地址重定向后可注销,但是并没有回调,只能重新输入地址进去登录,项目使用的是SpringSecurity,AbstractAuthenticationTargetUrlRequestHandler中的方法只有重定向的做法*/protected void handle(HttpServletRequest request, HttpServletResponse re...

html画三个重叠的矩形,html5 实现两个矩形的叠加_TiDB Robot的博客-程序员宅基地

注意要使用支持html5的浏览器Canvas Primer - Example: Drawing shadowswindow.addEventListener('load', function () {//得到canvas,并检测是否支持canvasvar elem = document.getElementById('myCanvas');if (!elem || !elem.getContex...

<算法导论>练习4.3_默默可书虫的博客-程序员宅基地

4.3-1用数学归纳法证明即可,思路是假设n&lt;=kn&lt;=kn&lt;=k时存在c使得T(k)&lt;=cn2T(k)&lt;=cn^2T(k)&lt;=cn2成立,只要证明出n=k+1n=k+1n=k+1时,存在c使得T(k+1)&lt;=c(k+1)2T(k+1)&lt;=c(k+1)^2T(k+1)&lt;=c(k+1)2。那么把T(k)和T(k−1)T(k)和T(k-1)T(k)和T(k−1)代入递归式得到:KaTeX parse error: Expected 'EOF', got

java中 自动输入一个按键_java中怎么实现键盘录入的功能-百度经验_ICOZ的博客-程序员宅基地

step4:新建一个Student类,设置类的各个成员变量,创建一个学生个人信息的方法。如下:public class Student { private String studentName; private String subject; private double result; private String eveluate; //创建一个信息输出方法 ...

centos7中java安装,CentOS7安装java8_weixin_39810196的博客-程序员宅基地

更新yumyum update查看是否已经安装了javajava -version如果以前已经安装就卸载查看内置的JDKrpm -qa | grep jdk卸载内置的JDKyum remove java-1.6.0-openjdk yum remove java-1.7.0-openjdk检查是否安装wget下载工具如果提示没有 wget 命令,那么必须先安装 wget 如下:yum instal...

跨平台的会员通 打通品牌任督二脉_博阳全渠道会员营销平台的博客-程序员宅基地

随着科技的发展,国民生活水平不断攀升,购物方式也发生了巨大的转变,年轻人越来越依赖线上的购物模式,一瓶水一包纸巾一件衣服都是从网上购买,淘宝、天猫、京东等头部的电商平台,也在不断为提升的购物体验而改造升级。互联网的不断扩张和升级,个人隐私问题受到了关注。2021年7月,国家关于隐私政策做了新的调整,同年8月,淘宝、天猫、京东等电商平台积极响应,随之做出了对应的调整。新的政策下来以后,给电商平台的商家们带来了非常大的不便。以往为了能提高会员留存率,商家同步天猫、京东、拼多多、抖店等第三方平台的订单信息

随便推点

qt5配置使用oracle,QT5环境编译Oracle数据库QOCI驱动程序_蛋疼得有理的博客-程序员宅基地

在线QQ客服:1922638专业的SQL Server、MySQL数据库同步软件准备:安装Qt5.6.3(安装MINGW版本或MSVC版本)安装VS2015(无需在msvc下编译驱动程序即可安装)安装oracle10g客户端,并且需要使用客户端中的lib/dll文件进行编译首先,在MSVC环境中进行编译编译环境:qt 5.6.3 + MSVC2015 32位oracle10g客户端win7 64位...

Java黑皮书课后题第6章:**6.3(回文整数)使用下面的方法头编写两个方法:……使用reverse方法实现isPalindrome。如果一个数字的逆序数和它自身相等,这个数就称为回文数。_有只程序猿的博客-程序员宅基地_使用下面的方法头编写两个方法

6.3(回文整数)使用下面的方法头编写两个方法:……使用reverse方法实现isPalindrome。如果一个数字的逆序数和它自身相等,这个数就称为回文数。题目题目概述破题:假设没有提示语句(待修改)代码运行示例题目题目概述6.3(回文整数)使用下面的方法头编写两个方法:// Return the reversal of an integer, e.g., reverse(456) returns 654public static int reverse(int number)// Retur

bootstrap未生效_基于SpringBoot bootstrap.yml配置未生效的解决_weixin_39616798的博客-程序员宅基地

我就废话不多说了,大家还是直接看代码吧~?12345org.springframework.cloudspring-cloud-contextorg.springframework.cloudspring-cloud-context补充知识:SpringBoot不读取bootstrap.yml/properties文件今天写创建了一个SpringBoot项目,配置文件从其他项目拷贝了一份boots...

python输出欢迎某某某_煎酿三宝适合在处暑食用_weixin_39715652的博客-程序员宅基地

【论述题】10月13日作业,包括设计主题海报、变形金刚海报、实验报告【填空题】Python语句print(float.as_integer_ratio(1.5))的输出结果是_______。【判断题】在面向对象程序设计中,函数和方法是完全一样的,都必须为所有参数进行传值。【简答题】下列Python语句的输出结果是___________。 def f():pass print(type(f()))【...

lnmp ubuntu mysql装不上_(亲测)ubuntu 下搭建 LNMP 开发环境(ubuntu18.04/php7.2/mysql5.7)..._weixin_39541844的博客-程序员宅基地

(最近在整理 web 后端相关的技术点,顺便记录下来备忘,会持续更新。嗯记笔记是个好习惯简单~)在 ubuntu18.04 下,搭建 LNMP 开发环境(php7.2、mysql5.7)1、安装 mysql5.7不选择 mysql 的安装版本,默认就是最新的 mysql,在这里最新版本是 mysql5.7 。$ sudo apt-get install mysql-server mysql-cli...

推荐文章

热门文章

相关标签