Самый быстрый способ найти количество меньших элементов справа от массива

Самый быстрый способ найти количество меньших элементов справа от массива
Самый быстрый способ найти количество меньших элементов справа от массива - florianolv @ Unsplash

В Daily Coding Problem, Miller&Wu поставили следующую задачу : Given an array of integers, return a new array where each element in the new array is number of smaller elements to the right of that element in the original input array.

Предлагаемое ими решение следующее (на языке python):

import bisect

def smaller_counts(lst):
   result = []
   seen = []
   for num in reversed(lst):
      i = bisect.bisect_left(seen, num)
      resul.append(i)
      bisect.insort(seen, num)
    return list(reversed(result))

Хотя алгоритм правильный, авторы затем утверждают, что это занимает O(n log(n)), что кажется мне неправильным: я ожидал бы, что вызов insort будет O(num), поскольку мы вставляем в массив и нам нужно переместить все элементы после num в правую часть этого массива. Это также подтверждается python doc.

В результате, я думаю, что общая стоимость составляет O(n^2).

Я что-то упустил, или авторы допустили здесь ошибку (вероятно, предполагая, что у insort будет такая же стоимость log(num), как и у bisect_left)?

Я также думал разместить это на code golf, но не был уверен, что ему там место.

Ваши рассуждения кажутся правильными

Выполнение n итераций над операцией O(n) означает общую сложность O(n²) в целом. Действительно ли вставка имеет временную сложность O(n), зависит от распределения данных. Например, если бы мы вставляли элементы в порядке возрастания (чтобы новые элементы только добавлялись без смещения существующих значений), то это могло бы быть так же дешево, как O (1). Однако этот сценарий не позволяет делать каких-либо предположений о распределении данных.

Обратите внимание, что решение O (n log n) возможно, если seen является структурой данных упорядоченного набора с вставкой O (log n), такой как сбалансированное двоичное дерево. Python не имеет подходящей структуры данных в стандартной библиотеке. Модуль heapq похож, но не может обеспечить здесь необходимые операции. Возможная ручная реализация может выглядеть так:

from dataclasses import dataclass
from typing import Optional, Tuple

def smaller_counts(lst: list[int]) -> list[int]:
    result = []
    seen = None
    for num in reversed(lst):
        location, seen = treeset_insert_and_get_location(seen, num)
        result.append(location)
    return list(reversed(result))

@dataclass
class Node:
    value: int
    size: int
    left: 'Optional[Node]' = None
    right: 'Optional[Node]' = None

    @property
    def left_size(self) -> int:
        if self.left is not None:
            return self.left.size
        return 0

    @property
    def right_size(self) -> int:
        if self.right is not None:
            return self.right.size
        return 0


def treeset_insert_and_get_location(
        tree: Optional[Node], value: int,
) -> Tuple[int, Node]:
    if tree is None:
        return 0, Node(value=value, size=1)

    if value < tree.value:
        location, tree.left = treeset_insert_and_get_location(
            tree.left, value)
        tree.size += 1
        return location, tree

    if value > tree.value:
        location, tree.right = treeset_insert_and_get_location(
            tree.right, value)
        tree.size += 1
        return tree.size - tree.right_size + location, tree

    assert tree.value == value
    tree.size += 1
    return tree.left_size, tree

full code incl. tests

На практике представленное решение в вопросе по-прежнему будет достаточно эффективным при меньших размерах ввода. Вставка O(n) — это операция, в которой современные компьютеры довольно хороши. Я ожидаю, что представленное решение или даже наивное решение O (n²) превзойдет любую древовидную структуру данных до нескольких сотен или нескольких тысяч элементов.


LetsCodeIt, 17 декабря 2022 г., 19:30