时间戳

首页 > 解决方案 > 在正确的索引处将整数添加到已排序的 ArrayList

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

问题描述

假设我有一个这样的排序列表（按升序排列）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)
}

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

标签： javasortingarraylist

解决方案

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

您可以在 O(log n) 时间内找到插入点Collections.binarySearch()，然后add()像现在一样调用。由于 O(log n + n) = O(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);

推荐阅读