Заданный массив для каждого элемента, узнать общее количество элементов, меньшее его, которые справа от него

Ответ 1

Его можно решить в O (n log n).

Если в BST вы сохраняете количество элементов поддерева, внедренных в этот node при поиске node (до достижения этого из корня), вы можете подсчитать количество элементов, большее или меньшее, чем в пути

int count_larger(node *T, int key, int current_larger){
    if (*T == nil)
        return -1;
    if (T->key == key)
        return current_larger + (T->right_child->size);
    if (T->key > key)
        return count_larger(T->left_child, key, current_larger + (T->right_child->size) + 1);
    return count_larger(T->right_child, key, current_larger)
}

** например, если это является нашим деревом, и мы ищем ключ 3, count_larger будет вызываться для:

- > (node 2, 3, 0)
- > (node 4, 3, 0)
--- > (node 3, 3, 2)

и окончательный ответ будет 2, как ожидалось.

Ответ 2

Предположим, что массив равен 6, -1,5,10,12,4,1,3,7,50

Шаги

1. Мы начинаем строить BST с правого конца массива. Поскольку нас интересуют все элементы, подходящие для любого элемента.

2. Предположим, что мы сформировали парное дерево решений до 10.

3. Теперь при вставке 5 мы обходим дерево и вставляем справа от 4. Обратите внимание, что каждый раз, когда мы проходим справа от любого node, мы увеличиваем на 1 и добавляем no. элементов в левом поддереве того, что node. например:
за 50 это 0   для 7 это 0       для 12 это 1 правое перемещение + левый размер 7 = 1 + 3 = 4
      для 10 таких же, как указано выше.
для 4 это 1 + 1 = 2

При построении bst мы можем легко поддерживать размер левого поддерева для каждого node, просто поддерживая соответствующую ему переменную и увеличивая ее на 1 каждый раз, когда node пересекает ее слева. Следовательно, решение Среднее значение O (nlogn).

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

Ответ 3

Я думаю, что можно сделать это в O(nlog(n)) с измененной версией quicksort. В основном каждый раз, когда вы добавляете элемент в меньшее, вы проверяете, является ли этот элемент рангом в исходном массиве, превосходящем ранг текущего стержня. Это может выглядеть как

oldrank -> original positions 
count -> what you want
function quicksort('array')
  if length('array') ≤ 1
      return 'array'  // an array of zero or one elements is already sorted
  select and remove a pivot value 'pivot' from 'array'
  create empty lists 'less' and 'greater'
  for each 'x' in 'array'
      if 'x' ≤ 'pivot' 
         append 'x' to 'less'
         if oldrank(x) > = oldrank(pivot)  increment count(pivot)
      else 
         append 'x' to 'greater'
         if oldrank(x) <  oldrank(pivot)  increment count(x) //This was missing
  return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

EDIT:

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

Оригинальный псевдокод в Википедии.

Ответ 4

Вы также можете использовать двоичное дерево индексов

int tree[1000005];
void update(int idx,int val)
{
   while(idx<=1000000)
   {
       tree[idx]+=val;
       idx+=(idx & -idx);
   }
}

int sum(int idx)
{
    int sm=0;
    while(idx>0)
    {
       sm+=tree[idx];
       idx-=(idx & -idx);
    }
    return sm;
}

int main()
{
    int a[]={4,2,1,5,3};
    int s=0,sz=6;
    int b[10];
    b[sz-1]=0;
    for(int i=sz-2;i>=0;i--)
    {
        if(a[i]!=0)
        {
            update(a[i],1);
            b[i]=sum(a[i]-1)+s;
        }
        else s++;
    }
    for(int i=0;i<sz-1;i++)
    {
       cout<<b[i]<<" ";
    }
   return 0;
}

Ответ 5

//some array called newarray
for(int x=0; x <=array.length;x++)
{
for(int y=x;y<array.length;y++)
{
if(array[y] < array[x])
{
newarray[x] = newarray[x]+1;
}
}
}

что-то вроде этого, где array - ваш входной массив и newarray ваш выходной массив убедитесь, что все правильно правильно (0 для значений newarrays)

Ответ 6

Другой подход без использования дерева.

• Построить другой отсортированный массив. Например, для входного массива {12, 1, 2, 3, 0, 11, 4} он будет {0, 1, 2, 3, 4, 11, 12}
• Теперь сравните положение каждого элемента из входного массива с отсортированным массивом. Например, 12 в первом массиве имеют индекс 0, а отсортированный массив - как 6
• После выполнения сравнения удалите элемент из обоих массивов

Ответ 7

Вы также можете использовать массив вместо двоичного дерева поиска.

def count_next_smaller_elements(xs):
    # prepare list "ys" containing item numeric order
    ys = sorted((x,i) for i,x in enumerate(xs))
    zs = [0] * len(ys)

    for i in range(1, len(ys)):
        zs[ys[i][1]] = zs[ys[i-1][1]]
        if ys[i][0] != ys[i-1][0]: zs[ys[i][1]] += 1

    # use list "ts" as binary search tree, every element keeps count of
    # number of children with value less than the current element value
    ts = [0] * (zs[ys[-1][1]]+1)
    us = [0] * len(xs)

    for i in range(len(xs)-1,-1,-1):
        x = zs[i]+1
        while True:
            us[i] += ts[x-1]
            x -= (x & (-x))
            if x <= 0: break

        x = zs[i]+1
        while True:
            x += (x & (-x))
            if x > len(ts): break
            ts[x-1] += 1

    return us

print count_next_smaller_elements([40, 20, 10, 50, 20, 40, 30])
# outputs: [4, 1, 0, 2, 0, 1, 0]

Ответ 8

Вместо BST вы можете использовать stl-карту.

Начните вставлять справа. После вставки элемента найдите его итератор:

auto i = m.find(element);

Затем вычтите его из m.end(). Это дает вам количество элементов на карте, которые больше текущего элемента.

map<int, bool> m;
for (int i = array.size() - 1; i >= 0; --i) {
  m[array[i]] = true;
  auto iter = m.find(array[i])
  greaterThan[i] = m.end() - iter;
}

Надеюсь, что это помогло.

Ответ 9

Кроме использования BST, мы также можем решить эту проблему оптимально, выполнив некоторую модификацию в алгоритме сортировки слиянием (в O (n * logn) time).

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

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

Ниже приведена программа python:

def mergeList(arr, pos, res, start, mid, end):
    temp = [0]*len(arr)
    for i in range(start, end+1):
        temp[i] = pos[i]

    cur = start
    leftcur = start
    rightcur = mid + 1

    while leftcur <= mid and rightcur <= end:

        if arr[temp[leftcur]] <= arr[temp[rightcur]]:
            pos[cur] = temp[leftcur]
            res[pos[cur]] += rightcur - mid - 1
            leftcur += 1
            cur += 1
        else:
            pos[cur] = temp[rightcur]
            cur += 1
            rightcur += 1

    while leftcur <= mid:
        pos[cur] = temp[leftcur]
        res[pos[cur]] += end - mid
        cur += 1
        leftcur += 1

    while rightcur <= end:
        pos[cur] = temp[rightcur]
        cur += 1
        rightcur += 1


def mergeSort(arr, pos, res, start, end):
    if start < end:
        mid = (start + end)/2
        mergeSort(arr, pos, res, start, mid)
        mergeSort(arr, pos, res, mid+1, end)
        mergeList(arr, pos, res, start, mid, end)


def printResult(arr, res):
    print
    for i in range(0, len(arr)):
        print arr[i], '->', res[i]


if __name__ == '__main__':
    inp = input('enter elements separated by ,\n')
    inp = list(inp)
    res = [0]*len(inp)
    pos = [ind for ind, v in enumerate(inp)]
    mergeSort(inp, pos, res, 0, len(inp)-1)
    printResult(inp, res)

Время: O (n * logn)

Пространство: O (n)