查找插入位置

我有一个整数ArrayList的整数。现在我有一个新的整数插入到ArrayList中。必须在适当的位置插入此新整数以保持ArrayList的排序顺序。查找插入位置

我可以只添加整数，然后使用Collections.sort（ArrayList）进行排序，但由于ArrayList太大，这种排序需要时间，我需要多次插入，所以我不想结束多次分拣，这会耗尽我的时间。

Collections.sort（）具有O（nlogn）（使用归并）。

我能有什么耗时少，或者我可以手动搜索要插入的花费最少的时间位置？

时间是高优先级。

感谢提前:)

来源

2013-10-06 Sravan2023

为什么不干脆在列表中，并在其适当的位置添加的元素。当你的list已经排序新list后insertion也将sorted，这将是一个O(N)操作。没有必要一遍又一遍地对列表进行排序。

编辑： - 现在这里有两件事情。如果您需要查找要插入到当前列表中的元素的位置，则可以使用Binary Search。实际上，在该位置插入该元素将需要跟随它的所有元素前移一个点为插入元素创建空间，我认为这比插入和重新排序更有效。

来源

2013-10-06 16:40:22 Prateek

实际上，我打算提出同样的问题，但我不确定如果我们在这个问题上误读了一些东西... – icedwater

谢谢。那是一个很好的工作，这是170秒到115，但我需要几乎到5秒。所以更有效率。 ?? – Sravan2023

您可以在'O（log N）'中找到元素必须使用'binary search'插入的位置复杂度 – Prateek

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

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

编辑：例与用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-06 16:47:27 Alowaniak

元素不是唯一的，所以不能使用TreeSet – Sravan2023

也可以解释我如何使用二分查找。如果我有一个元素，并想知道它的位置，我可以使用二进制搜索。但在这里我想知道插入的位置，所以我不明白我可以如何使用这个二进制搜索。如果我可以使用它会更有效。只是不明白我该怎么做 – Sravan2023

如果你搜索的元素不在列表中（所以你添加的元素），它会返回'（ - （插入点）-1）'。我仍然认为你会想要一个不同的数据结构，也许你可以使用'TreeMap'并且其值是元素的出现次数？ – Alowaniak

一个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); 
    } 
}

示例您可以使用自己的二进制搜索来估计新元素的位置，然后在良好的中置件

来源

2013-10-06 17:00:29 Sylwek

二进制搜索可用于查找列表中的现有元素。但是在这里我需要找到要插入的位置。那么我如何实现二进制搜索？ – Sravan2023

如果您使用'二进制搜索'来查找元素的位置，并且如果列表中没有这个元素，二进制搜索可以返回最后一个搜索索引 - 它将是您的元素应该在哪里估计的索引。然后你应该使用Inser Sort将你的元素放在正确的位置。例如：列表（1,2,3,4,6,7,8,9,10,11,12,13），你想把5列入列表二进制搜索将返回索引约3，然后你可以检查'list.get（3）'是否大于或小于你的元素，并且使用插入排序的方式是右/左 – Sylwek

查找插入位置

回答

相关问题