0

我有一个排序的整数数组列表。现在我有一个新的整数要插入到 ArrayList 中。这个新整数必须插入到适当的位置以保持 ArrayList 的排序。

我可以只添加整数，然后使用 Collections.sort(ArrayList) 对其进行排序，但由于 ArrayList 太大，这种排序需要时间，我需要插入很多次，所以我不想多次排序这会占用我的时间。

Collections.sort() 有 O(nlogn) （使用 mergeSort）。

我可以花更少的时间，或者我可以手动搜索要插入的位置，哪个需要最少的时间？

时间是重中之重。

提前致谢 ：）

4

3 回答 3

2

您可能需要考虑使用不同的数据结构（TreeSet如果可能的话），因为插入仍然会导致所有尾随元素移动。您可以使用它Collections.binarySearch来查找插入位置，它会返回：

返回： 搜索键的索引，如果它包含在列表中；否则，（-（插入点）- 1）。插入点定义为将键插入列表的点：第一个元素的索引大于键，如果列表中的所有元素都小于指定的键，则为 list.size()。请注意，这保证了当且仅当找到键时，返回值将 >= 0。

编辑：示例TreeMap

TreeMap<Integer, Integer> numbers = new TreeMap<>();
private void add(int n) {
    if(numbers.containsKey(n))
        numbers.put(n, numbers.get(n)+1);
    else
        numbers.put(n, 1);
}

private void remove(int n) {
    if(numbers.containsKey(n)) {
        int i = numbers.get(n);
        if(i == 1)
            numbers.remove(n);
        else
            numbers.put(n, i-1);
    }
}

示例List

List<Integer> numbers = new ArrayList<>();
private void add(int n) {
    int idx = Collections.binarySearch(numbers, n);
    if(idx < 0) {
        idx += 1;
        idx *= -1;
    }
    numbers.add(idx, n);
}

private void remove(int n) {
    numbers.remove(n);
}
于 2013-10-06T16:47:27.167 回答
1

为什么不直接浏览列表并将元素添加到适当的位置。因为你list已经排序新的list之后insertion也将是sorted，这将是一个O(N)操作。无需一遍又一遍地对列表进行排序。

编辑： - 现在这里有两件事。如果您需要找到应该将其插入当前列表的元素的位置，您可以使用Binary Search. 实际上，在该位置插入该元素将要求其后面的所有元素向前移动一个位置以为插入的元素创建空间，我认为这仍然比在后面插入并再次排序更有效。

于 2013-10-06T16:40:22.757 回答
0

您可以使用自己的二进制搜索来估计新元素的位置，然后将元素插入到合适的位置。

如果您使用binary search查找元素的位置并且如果列表中没有此元素，则二进制搜索可以返回搜索的最后一个索引 - 这将是您的元素应该在哪里的估计索引。然后你应该使用插入排序将你的元素放在正确的位置。

示例： LIST(1,2,3,4,6,7,8,9,10,11,12,13)​​ 并且您想将 5 放入列表二进制搜索将返回您的索引大约 3，然后您可以检查是否list.get(3)大于或小于您的元素并以右/左方式使用插入排序

于 2013-10-06T17:00:29.903 回答