将整数添加到已排序的 ArrayList 的正确索引处

Question

假设我有一个像这样的排序列表（按升序排列）ArrayList<Integer> arr = Arrays.asList(1, 2, 3, 5, 6)。列表中不会有重复项。

我想在正确的索引处添加一个整数，以便在添加元素后数组仍然排序，如下所示arr.add(4) // now arr = {1, 2, 3, 4, 5, 6}：

在通过使用或其他方式添加元素后，如何优雅地实现这一目标，而无需Collections.sort(arr)诉诸排序。

我正在寻找一种比我目前拥有的更好/更优雅的解决方案（我什至不知道它是否适用于所有情况哈哈）：

int n = 4 // number I want to add to the list
boolean added = false;

for(int i < 0; i < arr.size(); i++) {
   if(n < arr.get(i)) {
     arr.add(i, n)
     added = true;
     break;
   }
}

if(added == false) {
  arr.add(n)
}

我在这里先向您的帮助表示感谢！

Answer 1

您现在正在进行的线性搜索是 O(n)，加上调用 的 O(n) add()。

您可以使用 找到 O(log n) 时间内的插入点Collections.binarySearch()，然后add()像现在一样调用。总体复杂度仍然是 O(n)，因为 O(log n + n) = O(n)，但速度会稍微快一些，代码也会短一些。

int i = Collections.binarySearch(arr, n);

// `n` not found. Retrieve the insertion point from the return value.
if (i < 0) {
    i = -i - 1;
}

arr.add(i, n);