设计RandomPool结构

名字是乱打的

发布于 2022-05-13 09:44:44

2160

发布于 2022-05-13 09:44:44

文章被收录于专栏：软件工程

【题目】 设计一种结构，在该结构中有如下三个功能： insert(key)：将某个key加入到该结构，做到不重复加入。 delete(key)：将原本在结构中的某个key移除。 getRandom()：等概率随机返回结构中的任何一个key。 【要求】 Insert、delete和getRandom方法的时间复杂度都是 O(1)

实现思路 借助两个hashmap,加一个位置索引来实现其中一个hashmap把值放在key中,位置索引放在value中另外一个hashmap把值放在value中,位置索引放在key中

insert(key):两个均添加,但是值和健相反 getRandom():这样当我们随机取数据时候,只要取一个0~index的随机数,就可以从hashmap2中取数据了 delete(key) 由于我们删除数据时候会产生很多索引没有值的现象,那么我们随机得到的可能是空值,所以我们这里采用的方法是,当删除元素时候,将最后一个索引的值添到删除的索引里取代码

package com.algorithm.practice.hash;

import java.util.HashMap;

public class RandomPool {
    public HashMap<String,Integer> hashMap1;
    public HashMap<Integer,String> hashMap2;
    public int index;
    public RandomPool(){
     hashMap1=new HashMap<>();
     hashMap2=new HashMap<>();
        index =0;
    }
    public  void  insert(String key){
        if (!hashMap1.containsKey(key)) {
            hashMap1.put(key, index);
            hashMap2.put(index, key);
            index++;
        }}
    public  String  getRandom(){
        if (index==0){
            return null;
        }
       int index1=(int) Math.random()*index;//0~size-1
        return hashMap2.get(index1);
    }
    public  void   delete(String key){
        Integer index = hashMap1.get(key);//要删除的索引位置
        hashMap1.remove(key);//删除hash1上的值
        hashMap2.remove(index);//删除hash2上的值
        String lastValue = hashMap2.get(index);//得到最后一个索引的值
        hashMap1.remove(lastValue); //将最后一个索引的值填到刚刚两个hashmap删除的位置
        hashMap1.put(lastValue,index);
        hashMap2.remove(index);
        hashMap2.put(index,lastValue);
        index--;

    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-13，如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap