如何快速插入一个元素到数组的重复后，所有相等的元素

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++;

需要注意的是，该元素必须插入到元素链中depth值相等的特定位置——在该链的末尾。这就是为什么在二分查找之后我需要额外的两个while循环，我认为这不会太昂贵，因为二分查找给了我这个位置的近似值。

我仍然想知道是否有一些更好的解决方案或一些已知的算法对于这样的问题，我还没有听说过?也许使用不同于ArrayList的数据结构?目前，我忽略了最坏情况下的插入O(n)(插入在开始或中间)，因为使用正常的List，我无法找到使用上面方法插入的索引。

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);

Answer 2

一种方法是进行减半搜索，其中第一次搜索是列表的一半(list.size()/2)，然后对于下一次搜索可以执行该列表的一半，依此类推。使用这种指数方法，当您有4096个对象时，您只需要进行12次搜索，而不是进行4096次搜索。

很抱歉完全无视专业术语，我不擅长术语:p

Answer 3

除非我忽略了一些东西，否则你的方法基本上是正确的(但有一个错误，见下文)，在某种意义上，你的第一个while试图计算插入索引，这样它将被放置在所有较低的OR EQUAL Z之后:在你的第一个测试中正确地有一个等号(更新"start"如果它产生TRUE)。

那么，当然，就没有必要再担心它在同类中的位置了。然而，你的后续while破坏了这种良好的情况:第一个后续while中的测试总是产生TRUE(一次)，所以你返回;然后你需要第二次跟进来撤销它。所以，你应该删除这两个后续时间，你就完成了…

然而，你的第一个while有一个小问题，它并不总是完全符合你的目的。我猜是错误的结果促使你实施后续行动，同时"修复"它。

这是你的问题。假设你有一个try-index (start+end)/2，它指向一个更大的Z，但就在它的值Z之前，然后进入第二个测试(elseif)，并将"end"设置为Z值所在的位置。最后你就得到了那个位置。补救方法很简单:在您的elseif赋值中，放入"end = index"(不带-1)。最后的注释:在elseif中的测试是不必要的，只要else就足够了。

所以，总的来说，你得到

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
        end = index;
}

(我希望我没有忽略一些小事…)

Answer 4

键的最低位加1(带进位);对插入位置进行二分查找;然后插入到这里。

您的二进制搜索必须被构造成在重复序列的最左边结束，但这是微不足道的，因为了解了各种二进制搜索算法。