Блог

Я должен найти (или, по крайней мере, подсчитать) все пары (не обязательно смежных) несортированных элементов в частично отсортированном массиве.

Если мы предположим, что сортировка будет по возрастанию , то в массиве [1 4 3 2 5] будут следующие несортированные пары: (4, 3) , (3, 2) и (4, 2) .

Я думаю об алгоритме, который работает по принципу сортировки вставки, поскольку сортировка вставки имеет тенденцию сравнивать каждый новый элемент со всеми элементами, которые неуместны по отношению к новому элементу.

Редактировать: Публикуя вопрос, я не понимал, что поиск пар будет иметь более высокую временную сложность, чем их подсчет. Существует ли лучший возможный алгоритм, который просто подсчитывает, сколько таких пар существует?

Это немного зависит от того, что именно вы подразумеваете под «частично отсортированным» — можно утверждать, что каждый массив в какой-то степени частично отсортирован.

Поскольку этот алгоритм в любом случае имеет наихудшую сложность O(n^2) (считайте, что входные данные отсортированы в порядке убывания), вы также можете пойти по прямому маршруту:

 ret = []

for i in range(len(array)):
    for j in range(i, len(array)):
        if array[i] > array[j]:
            ret.append((array[i], array[j]))

return ret
 

Это очень хорошо работает для случайных массивов.

Однако я полагаю, что вы имеете в виду нечто большее, чем то, что внутри массива есть большие участки, где сортируются числа, но это не относится к массиву в целом.

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

Вот реализация на Python того, что я имею в виду:

 # find all sorted stretches
stretches = []
begin = 0
for i in range(1, len(array)):
    if array[i-1] > array[i]:
        stretches.append(array[begin:i])
        begin = i
if i 1 > begin:
    stretches.append(array[begin:])

# compare stretches
ret = []
for i in range(len(stretches)):
    stretchi = stretches[i]
    stretchi_rev = None
    
    for j in range(i 1, len(stretches)):
        stretchj = stretches[j]

        if stretchi[-1] > stretchj[0]:
            if stretchi_rev is None:
                stretchi_rev = list(reversed(stretchi))

            hi = len(stretchj)
            for x in stretchi_rev:
                i = bisect.bisect_left(stretchj, x, 0, hi)
                if i == 0:
                    break
                else:
                    for y in stretchj[:i]:
                        ret.append((x, y))
                    hi = i
        
return ret
 

Для случайных массивов это будет медленнее, чем при первом подходе. Но если массив большой, а количество частично отсортированных частей достаточно велико, этот алгоритм в какой-то момент начнет превосходить поиск методом перебора.

Как предложил @SomeDude в комментариях, если вам просто нужно посчитать пары, есть O(nlogn) решение, основанное на построении бинарного дерева поиска. Здесь есть некоторые тонкости — нам нужно отслеживать количество дубликатов ( ic ) на каждом узле, и по соображениям производительности мы также отслеживаем количество правильных дочерних элементов ( rc ).

Основная схема вставки значения v в дерево, корни которого находятся в узле n , такова:

 def insert(n, v)
  if v < n.data
    count = 1   n.ic   n.rc
    if n.left is null
      n.left = node(v)
      return count
    return count   insert(n.left, v)
  else if v > n.data
    if n.right is null
      n.right = node(v)
      n.rc = 1
      return 0
    n.rc  = 1
    return insert(n.right, v)
  else // v == n.data
    n.ic  = 1
    return n.rc
 

А вот немного функционирующего Java-кода (Ideon):

 static int pairsCount(Integer[] arr) {
    int count = 0;
    Node root = new Node(arr[0]);
    for(int i=1; i<arr.length; i  )
        count  = insert(root, arr[i]);
    return count;
}

static int insert(Node n, int v) {
    if(v < n.value) {
        int count = 1   n.rc   n.ic;
        if(n.left == null) {
            n.left = new Node(v);
            return count;
        }
        return count   insert(n.left, v);
    } 
    else if(v > n.value) {
        if(n.right == null) {
            n.right = new Node(v);
            n.rc = 1;
            return 0;
        }
        n.rc  = 1;
        return insert(n.right, v);
    }
    else {
        n.ic  = 1;
        return n.rc;
    }
}

static class Node {
    int value;
    Node left, right;
    int rc; // right children count
    int ic; // duplicate count
    
    Node(int value) {
        this.value = value;
    }
}
 

Тест:

 Integer[] arr = {1, 4, 3, 2, 5};
System.out.println(pairsCount(arr));
 

Выход:

 3