java - 如何在所有相等元素之后快速将元素插入到具有重复项的数组中？

Question

我有一个 ArrayList，其中包含按“Z”( float )位置从低到高排序的游戏对象。我不确定 ArrayList 是否是它的最佳选择，但我想出了这样一个解决方案，可以比线性(最坏情况)更快地找到复杂度的插入索引:

        GameObject go = new GameObject();
        int index = 0;
        int start = 0, end = displayList.size(); // displayList is the ArrayList
        while(end - start > 0)
        {
            index = (start + end) / 2;
            if(go.depthZ >= displayList.get(index).depthZ)
                start = index + 1;
            else if(go.depthZ < displayList.get(index).depthZ)
                end = index - 1;
        }
        while(index > 0 && go.depthZ < displayList.get(index).depthZ)
            index--;
        while(index < displayList.size() && go.depthZ >= displayList.get(index).depthZ)
            index++;

要注意的是，元素必须插入到具有相同深度 Z 值的元素链中的特定位置 - 在该链的末尾。这就是为什么在二分搜索之后我需要 2 个额外的 while 循环，我认为这不会太昂贵，因为二分搜索给了我这个地方的一些近似值。

我仍然想知道是否有更好的解决方案或一些我从未听说过的已知算法来解决此类问题？也许使用与 ArrayList 不同的数据结构？目前我忽略了最坏情况下的插入 O(n)(在开头或中间插入)，因为使用普通列表我将无法使用上面的方法找到要插入的索引。

Answer 1

你应该尝试使用平衡搜索树(例如红黑树)而不是数组。首先你可以尝试使用TreeMap里面的红黑树，看看是否满足你的要求。可能的实现:

Map<Float, List<Object>> map = new TreeMap<Float, List<Object>>(){
    @Override
    public List<Object> get(Object key) {
        List<Object> list = super.get(key);
        if (list == null) {
            list = new ArrayList<Object>();
            put((Float) key, list);
        }
        return list;
    }
};

使用示例:

map.get(0.5f).add("hello");
map.get(0.5f).add("world");
map.get(0.6f).add("!");
System.out.println(map);