遵循只能增加的值集合中的最小值

Question

我有一大堆整数，它们的值只会增长（我在数东西）。

为了效率起见，我单独保留了一个最大值，需要时更新：

// when increasing the i'th count
coll[i] += 1;
// check whether also to update the max:
if(coll[i] > max){
  max = coll[i];
}

什么是同时 "follow" 集合的 最小值 值的有效算法？

我的意思是高效，尽可能少地迭代整个集合并保持小的内存占用。（后者真的不如前者重要）

我正在使用 Java：因此，如果 JRE 中已经包含上述算法，欢迎提供参考。

Answer 1

为每个值保留计数的散列 table，然后更新它，如果散列 table 中没有更多等于 min 的值，则更新最小值。

// when increasing the i'th count
coll[i] += 1;
--hashTable[coll[i] - 1];
++hashTable[coll[i]];
// check whether also to update the max:
if(coll[i] > max){
  max = coll[i];
}
// check whether to update the min:
if(min == coll[i] - 1 && hashTable[coll[i] - 1] == 0){
  min = coll[i];
}

哈希 table 可以是一个简单的数组，如果你能负担得起内存（如果你的值足够小）或实际的 Hashtable.

这只需要对您的集合进行初始迭代来构建哈希 [=19=]。然后将不再执行迭代。

遵循只能增加的值集合中的最小值

Follow the minimum value in a collection of values which can only increase

java

algorithm

collections

min