[数据结构与算法] 398. Random Pick Index

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 398. Random Pick Index -> 正文阅读

[数据结构与算法]398. Random Pick Index

果然还是得研究有难度的题目，才会收获更大

public class Solution {
    Map<Integer,String> saveOneToNHashMap=new HashMap<Integer,String>();
    public Solution(int[] nums){

        for(int i=0;i<nums.length;i++){
            if(saveOneToNHashMap.containsKey(nums[i])){
                String indexString=saveOneToNHashMap.get(nums[i]);
                saveOneToNHashMap.put(nums[i],indexString+i);
            }else{
                saveOneToNHashMap.put(nums[i],i+"");
            }
        }

    }
    public int pick(int target){
        String indexStr=saveOneToNHashMap.get(target);

        int index=new Random().nextInt(indexStr.length());

        char resultIndex=indexStr.charAt(index);


        return (int)resultIndex-(int)'0';
    }
}

这个是我一开始的做法，但是String的长度是有限制的，一个字符串的长度大于65535就会报错，

在相同思路的做法下，官方的解题思路是将String换成了List<Integer>.

class Solution {
    Map<Integer, List<Integer>> pos;
    Random random;

    public Solution(int[] nums) {
        pos = new HashMap<Integer, List<Integer>>();
        random = new Random();
        for (int i = 0; i < nums.length; ++i) {
            pos.putIfAbsent(nums[i], new ArrayList<Integer>());
            pos.get(nums[i]).add(i);
        }
    }

    public int pick(int target) {
        List<Integer> indices = pos.get(target);
        return indices.get(random.nextInt(indices.size()));
    }
}