Найти местоположение вставки

Question

У меня есть отсортированный массив ArrayList целых чисел. Теперь у меня есть новое целое число для вставки в ArrayList. Это новое целое число должно быть вставлено в соответствующее положение, чтобы сохранить ArrayList в отсортированном порядке.

Я могу просто добавить целое число, а затем отсортировать его с помощью Collections.sort (ArrayList), но поскольку ArrayList слишком велик, этот вид занимает много времени, и мне нужно вставить много раз, поэтому я не хочу заканчивать сортировка несколько раз, что будет съедать мое время.

Collections.sort() имеет O (nlogn) (использует mergeSort).

Могу ли я иметь что-то меньшее, чем занятно, или я могу вручную найти позицию для вставки, которая занимает наименьшее время?

Время имеет высокий приоритет.

Заранее спасибо :)

Answer 1

Почему бы не просто идти по списку и добавить элемент в соответствующее положение. Поскольку ваш list уже отсортирован, новый list после insertion также будет sorted, и это будет операция O(N). Нет необходимости сортировать список снова и снова.

EDIT: - Теперь здесь есть две вещи. Один, если вам нужно найти местоположение элемента, в который он должен быть вставлен в текущий список, который вы можете сделать с помощью Binary Search. Фактически, вставка этого элемента в это место потребует всех элементов, которые следуют за ним, чтобы переместить одно пятно вперед, чтобы создать пространство для вставленного элемента, который, по моему мнению, еще эффективнее, чем вставка назад и сортировка снова.

Answer 2

Возможно, вы захотите рассмотреть возможность использования другой структуры данных (например, TreeSet), так как вставка все равно приведет к смещению всех перемещаемых элементов. Вы можете использовать Collections.binarySearch, чтобы найти место для вставки, хотя, который возвращает:

Возвраты: Индекс ключа поиска, если он содержится в списке; в противном случае (- (точка ввода) - 1). Точка вставки определяется как точка, в которой ключ будет вставлен в список: индекс первого элемента больше ключа или list.size(), если все элементы в списке меньше указанного ключа. Обратите внимание, что это гарантирует, что возвращаемое значение будет> = 0 тогда и только тогда, когда ключ найден.

EDIT: Пример с 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); 
} 

Answer 3

Вы можете использовать свой собственный бинарный поиск, чтобы оценить позицию нового элемента, а затем вставить элемент в хорошем позиция