1

我有一个号码long nbr = 10000。我正在增加和减少它，增加或减少的量取决于它的值。如果nbr > x，则 nbr += xx，如果nbr > y，则 nbr += yy 等。根据其他因素，增量值（xx、yy 等）将发生变化，并且增量值变化的限制（x、y 等） ） 将改变。我想要一个函数 public int increaseNbr(int nbr) 根据上述逻辑返回一个递增的数字，并尽可能高效地执行此操作。目前我正在像下面这样实现它，但我觉得它不是很有效。

private TreeMap<Integer, Integer> aboveNbr_increment_map;

private Integer getIncrementValueAboveNbr(int nbr) {

    // finds the valid increment below a certain price
    Map.Entry<Integer, Integer> entry = aboveNbr_increment_map.lastEntry();

    while (entry != null) {

        if (price>=entry.getKey()) {
            return entry.getValue();
        }

        entry = aboveNbr_increment_map.lowerEntry(entry.getKey());
    }

    // otherwise return the lowest increment size
    return aboveNbr_increment_map.get(aboveNbr_increment_map.firstKey());
}

    public Integer getNextNbrAbove(int nbr) {

        return nbr + this.getIncrementValueAboveNbr(nbr));
    }
4

2 回答 2

2

您可以floorEntry通过查找下限在对数时间内完成。

private TreeMap<Integer, Integer> aboveNbr_increment_map;

private Integer getIncrementValueAboveNbr(int nbr) {

    Entry<Integer, Integer> entry = aboveNbr_increment_map.floorEntry(nbr);

    if(entry != null) {
        return nbr + entry.getValue();
    }

    return aboveNbr_increment_map.get(aboveNbr_increment_map.firstKey());
}

在此之前将键值存储在TreeMap这样的位置 -

aboveNbr_increment_map.put(x + 1, xx);
aboveNbr_increment_map.put(y + 1, yy);

您需要存储x + 1而不是x因为floorEntry返回小于或等于给定键的最大键。在这里，当nbrvalue 为时，我们正在增加> x。

希望能帮助到你！

于 2017-03-24T19:24:24.220 回答
2

您的 TreeMap 方法的复杂度为 log(N)，其中 N 是边界数。如果边界的数量足够小，这可能是完全可以接受的。

您在评论中提到您的号码空间相当有限。只有一百万个可能的数字，您还可以使用数字作为索引构建一个查找表（数组）。这会给你 O(1)，但查找表确实会产生自己的构建成本和内存消耗。

根据表更改之间的查找次数，查找表可能更快或更慢。

除非您的程序在其运行时调用 getIncrementValueAboveNbr() 中花费了相当大的一部分，否则您可能会浪费您的时间。分析使用该方法的任何东西，并且只有当这表明在那里花费了大量时间时才考虑重写它。

于 2017-03-24T19:40:22.213 回答