在 Java 中，我希望能夠始終保持按物種排序的魚類集合（因此使用了 HashMap），同時能夠從所有物種中選擇一個隨機元素，除了具有恒定時間復雜度的物種。例如，下面的代碼完成了這項作業，但復雜度為 O(number of elements) ：
import java.util.*;
HashMap<String, ArrayList<Fish>> fishesBySpecies = new HashMap<>();
// Insert some fishes...
// Fish has a String attribute that describes its species
// Now we want to pick a random Fish that isn't from the unwantedSpecies
String unwanted = "unwanted species";
ArrayList<Fish> wantedSpecies = new ArrayList<>();
for (String species : fishesBySpecies.keySet()) {
if (!Objects.equals(species, unwanted)) {
wantedSpecies.addAll(fishesBySpecies.get(species));
}
}
// Finally !
int randomIndex = new Random().nextInt(wantedSpecies.size());
Fish randomElement = wantedSpecies.get(randomIndex);
如果可能的話，知道如何以恒定的時間復雜度做到這一點嗎？謝謝 ！
uj5u.com熱心網友回復：
你正在執行的是過濾，過濾的時候你要檢查每個元素是否需要取出。您可以嘗試對鍵使用字母排序，并在鍵按字母順序大于過濾（不需要的）鍵時停止過濾。
您的代碼也可以通過使用 java 流徹底縮短：
HashMap<String, ArrayList<Fish>> fishesBySpecies = new HashMap<>();
// Insert some fishes...
// Fish has a String attribute that describes its species
// Now we want to pick a random Fish that isn't from the unwantedSpecies
String unwanted = "unwanted species";
fishesBySpecies.keySet().stream() // Get the keyset and create a stream out of it
.filter(key -> !key.equalsIgnoreCase(unwanted)) // If key is not equal to unwanted then leave it in else remove it
.forEach(filteredKey ->
wantedSpecies.addAll(fishesBySpecies.get(filteredKey))); // For each key that was left in, we fetch the fishes
或者
fishesBySpecies.keySet().stream() // Get the keyset and create a stream out of it
.forEach(key ->
{
if(!key.equalsIgnoreCase(unwanted))
{
wantedSpecies.addAll(fishesBySpecies.get(unwanted));
}
}
); // iterate and filter at the same time. Faster.
uj5u.com熱心網友回復：
我能想到的唯一方法是維護ArrayList<Fish>你已經擁有的地圖。但是有一個缺點：添加或洗掉魚會稍微復雜一些：
Map<String, List<Fish>> fishesBySpecies = new HashMap<>();
List<Fish> wantedFishes = new ArrayList<>();
//...
public void addFish(String species, Fish fish) {
List<Fish> speciesFishes = fishesBySpecies.get(species);
if (speciesFishes == null) {
speciesFishes = new ArrayList<>();
fishesBySpecies.put(species, speciesFishes);
}
speciesFishes.add(fish);
// also maintain the list of wanted fishes
if (!unwantedSpecies.equals(species)) {
wantedFishes.add(fish);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/394590.html
上一篇：Swift5結構陣列中的嵌套排序