Блог

Этот пример демонстрирует, как определить индекс, по которому элемент должен быть вставлен в отсортированный список. Хотя BinarySearch() используется для поиска существующих элементов, его также можно использовать для определения индекса вставки для несуществующих элементов.

 // Create a list with an ordered list of items 
List sortedList = new LinkedList(); 
sortedList.addAll(Arrays.asList(new String[]{"ant", "bat", "cat", "dog"}));
// Search for the non-existent item int index = Collections.binarySearch(sortedList, "cow"); 
// -4 // Add the non-existent item to the list 
if (index < 0) { sortedList.add(-index-1, "cow"); } 
  

Как я не могу вставлять элементы за время O (k log k n).
k — это количество списков.
n — общее количество элементов во всех списках (n = n1 n2 … nk).

Объясните, что такое асимптотический анализ алгоритмов???

Похоже, это заслуживает пометки «домашнее задание», поэтому я не буду портить вам его полностью, но просмотрите ваши очень классические алгоритмы сортировки и не думайте об этом как о вставке элементов, думайте об этом как о создании упорядоченного списка, который содержит все элементы из обоих списков.