如何根据O（n）时间内其他值的Map中的Integer值随机选择一个键？ [英] How to randomly select a key based on its Integer value in a Map with respect to the other values in O(n) time?

问题描述

如果我们有一个 Map< T，Integer> ，我们假设整数值表示有多少Ts。因此，我想根据其整数值统一选择一个T。如果地图包含a= 4和b= 6的字符串，那么我想要它，以便选择40％的时间a，并选择60％的时间b。

If we have a Map<T, Integer>, let's say the Integer value represents "how many" Ts there are. Thus, I want to uniformly select a T based on its Integer value. If the map contains Strings with "a"=4 and "b"=6, then I want it so that 40% of the time "a" is selected and 60% of the time "b" is selected.

最重要的是，我想在这个O（n）中，n是两个（不是十）在我以前的例子。我最初做了一个包含键的ArrayList，它有多少值（并且简单地返回任何随机索引），但是这个过程不仅非常慢，而且对于 Map< T，Integer> 表示。

Most importantly, I'd like this in O(n), n being two (not ten) in my previous example. I originally made an ArrayList containing the keys by how many values it had (and simply returning any random index), but this process is not only very slow, but completely counterintuitive for what the Map<T, Integer> represents.

推荐答案

OP这里。

我想出了一个优雅的解决方案！对于任何误解：我原来的想法是将所有的键存储在一个ArrayList中有多少值完全忽略了使用Map来存储使用整型的实例的点;任何类似的解决方案都会适得其反！假设地图是无序的，这里是我的解决方案：

I came up with an elegant solution! For any misunderstandings: My original idea of storing all the keys by how many values in an ArrayList was completely disregarding the point of using a Map to store "instances of the Key using Integers"; any similar solutions are counterproductive! Assuming the Map is unordered, here is my solution:

public T randomPick(Random r) {

        int randomValue = r.nextInt(size());
        int currentSum = 0;
        T lastElement = null;

        for (T t : map.keySet()){
            if (randomValue < currentSum + map.get(t)){
                return t;
            }
            currentSum+= map.get(t);
            lastElement = t;
        }
        return lastElement;
    }

它比较随机值与当前总和+当前元素的值。如果不到，我们返回当前的密钥。否则，继续追加这个价值。如果是这样，随机值不会小于任何值，我们返回 lastElement 。

It compares the random value with a current sum + the current element's value. If it is less than that, we return the current key. Else, keep going and add that value to the sum. If it is the case such that the random value is never less than any of the values, we return the lastElement.

希望这可以清除。

这篇关于如何根据O（n）时间内其他值的Map中的Integer值随机选择一个键？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！