Dada una matriz A con n valores, sea X de A una matriz que contiene en el índice i el número de elementos que son más grandes que A[i] y están a su derecha en la matriz original A
Por ejemplo, si A era: [10,12,8,17,3,24,19] , entonces X(A) es: [4,3,3,2,2,0,0]
¿Cómo puedo resolver esto en O(n log(n)) Tiempo y O(n) Complejidad espacial?
Puedo resolver esto fácilmente en O(n^2) Tiempo y O(1) Espacio usando un ciclo y, para cada elemento, contando cuántos elementos son más grandes que el del lado derecho, pero no tuve éxito con esos requisitos
Estaba pensando en usar la ordenación rápida con se puede hacer en O(n log(n)) en el peor de los casos, pero no veo cómo la matriz ordenada podría ayudar aquí.
Nota: Con respecto a la ordenación rápida, el algoritmo necesita algunos ajustes para asegurar O(n log(n)) en el peor de los casos y no solo en el promedio.
algo similar a merge sort donde se inserta el conteo después de procesar a la derecha y antes de procesar el lado izquierdo del rango, por ejemplo:
#include <algorithm> #include <functional> void count_greater_on_right( int* a, int* x, int begin, int end ) { if( end - begin <= 2 ) { if( end - begin == 2 && a[begin] < a[begin+1] ) { x[begin]+=1; // specific std::swap( a[begin], a[begin+1] ); } return; } int middle =(begin+end+1)/2; count_greater_on_right( a, x, middle, end ); // specific { for( int i=begin; i!=middle; ++i ) { x[i]+=std::lower_bound( &a[middle], &a[end], a[i], std::greater<int>() )-&a[middle]; } } count_greater_on_right( a, x, begin, middle ); std::inplace_merge( &a[begin], &a[middle], &a[end], std::greater<int>() ); }el código, específico de la tarea, se comenta con // specific; el orden inverso de clasificación lo hace un poco más simple en mi humilde opinión; actualiza 'a', por lo que si necesita una secuencia original, cree una copia.