[Algo] Constant Time Random Picker 获取集合内随机元素

calx 发布于2019-08-14 16:16 / 1219人阅读

摘要：但是这功能有要求我们必须保持内容的有序，这样我们才能通过随机数的方法得到随机的某个元素。取得随机数的话，则是在当前数组有效范围内取随机数就行了。

Constant Time Random Picker

设计一个数据结构，支持O(1)时间的查询，增加，删除，和得到其中随机元素的操作，可以认为其中的元素是数字。

哈希表数组 复杂度

时间 O(1) 空间 O(N)

思路

要求O(1)时间查询和删除，则想到哈希表，其他的数据结构都要遍历一遍才行。但是getRandom这功能有要求我们必须保持内容的有序，这样我们才能通过随机数的方法得到随机的某个元素。这里我们可以用数组、链表或者树保持有序，但是链表得到第n个元素要O(N)的时间，而树也要logN时间，所以不适合，只有数组。用数组的技巧在于，数组只是保持一个顺序，我们可以哈希表表示一个元素和其在数组中下标的映射关系，保证我们的O(1)查询。而对于删除，我们需要维护一个length变量（用表的大小也行），然后每次删除的时候把要删的数和数组当前标记的“最后”一个元素交换，然后把大小减一，并更新哈希表。取得随机数的话，则是在当前数组有效范围内取随机数就行了。

代码

public class RandomPicker {
    Random r;
    ArrayList arr;
    HashMap map;
    int length;
    
    public RandomPicker(){
        this.r = new Random();
        this.arr = new ArrayList<>();
        this.map = new HashMap<>();
        this.length = 0;
    }
    
    public void add(int key){
        arr.add(length, key);
        map.put(key, length);
        length++;
    }
    
    public void delete(int key){
        // 将要删的数和最后一个交换
        int idx = map.get(key);
        int tmp = arr.get(length - 1);
        arr.set(length - 1, key);
        arr.set(idx, tmp);
        // 更新元素和下标的对应关系
        map.put(tmp, idx);
        length--;
    }
    
    public int getRandom(){
        return arr.get(r.nextInt(length));
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66175.html

基于K-means 切割多边形 JAVA实现

摘要：基于切割多边形实现思路初稿详见多边形等分依赖实现实现过程结果类泰森多边形平分多边形结果原始平面随机点集合分组后组中心集合构造泰森多边形聚合类聚合聚合总量数据集合簇族数量中基于K-means 切割多边形 JAVA实现思路初稿详见多边形等分依赖 geotools ekmeans org.locationtech.jts jts-co...

haobowd 2019-08-16 14:30 评论0 收藏0
surprise库文档翻译

摘要：默认值为返回值，一个对象，包含了原生用户原生项目真实评分预测评分可能对后面预测有用的一些其他的详细信息在给定的测试集上测试算法，即估计给定测试集中的所有评分。这里的格式并没有做过多的处理，可参考于OneNote笔记链接由于OneNote取消了单页分享，如果需要请留下邮箱，我会邮件发送pdf版本，后续再解决这个问题推荐算法库surprise安装 pip install surp...

JessYanCoding 2019-07-31 10:25 评论0 收藏0
Tensorflow Python API 翻译（constant_op）

摘要：随机数张量提供了一些函数，去帮助我们构建随机数张量。该值表示正态分布的均值。一个维的，或者一个数据类型是的值，该值表示正态分布的标准偏差。解释这个函数返回一个随机数序列，数组里面的值按照均匀分布，数据范围是。作者：chen_h微信号 & QQ：862251340微信公众号：coderpai简书地址：https://www.jianshu.com/p/d05... 计划现将 tens...

godlong_X 2019-07-30 15:25 评论0 收藏0
AOP实践: Java利用注解和反射实现一个方便的函数性能测量工具

摘要：实现先看实现之后的效果测试类运行输出如下可以看到此时加了注解的和的运行时间被统计了，而没加的未被统计在内。思路修改，在之前的中返回一个，储存方法名耗时的键值结构。然后降序排序返回一个。最后遍历根据百分比求得各个方法的并输出相关信息。最初目的在学习Java的集合类时，有时候想要测试代码块的运行时间，以比较不同算法数据结构之间的性能差异。最简单的做法是在代码块的前后记录时间戳，最后相减...

zhangke3016 2019-08-14 14:55 评论0 收藏0