c++ - trabajar - programa de matrices en c

Elemento de la mayoría-partes de una matriz

Question

Tengo una matriz llena de números enteros. Mi trabajo es encontrar elementos de la mayoría rápidamente para cualquier parte de una matriz, y tengo que hacerlo ... log n time , no lineal, pero de antemano puedo tomarme un tiempo para preparar la matriz.

Por ejemplo:

1 5 2 7 7 7 8 4 6

Y consultas:

[4, 7] devuelve 7

[4, 8] devuelve 7

[1, 2] devuelve 0 (sin elemento de mayoría), y así sucesivamente ...

Necesito tener una respuesta para cada consulta, si es posible, debe ejecutarse rápidamente.

Para la preparación, puedo usar el tiempo O (n log n)

Answer 1

En realidad, se puede hacer en tiempo constante y espacio lineal (!)

Ver https://cs.stackexchange.com/questions/16671/range-majority-queries-most-freqent-element-in-range y S. Durocher, M. He, I Munro, PK Nicholson, M. Skala, Range mayoría en tiempo constante y espacio lineal, Information and Computation 222 (2013) 169-179, Elsevier.

Su tiempo de preparación es O (n log n), el espacio necesario es O (n) y las consultas son O (1). Es un documento teórico y no pretendo entenderlo todo, pero parece imposible de implementar. Están usando árboles wavelet .

Para una implementación de árboles wavelet, consulte https://github.com/fclaude/libcds

Answer 2

Las consultas O (log n) y el preprocesamiento / espacio O (n log n) se pueden lograr al encontrar y usar intervalos mayoritarios con las siguientes propiedades:

1. Para cada valor de la matriz de entrada puede haber uno o varios intervalos de la mayoría (o puede no haber ninguno si los elementos con estos valores son demasiado escasos, no necesitamos intervalos de la mayoría de longitud 1 porque pueden ser útiles solo para intervalos de consulta de tamaño 1 que se manejan mejor como un caso especial).
2. Si el intervalo de consulta se encuentra completamente dentro de uno de estos intervalos de mayoría , el valor correspondiente puede ser el elemento de la mayoría de este intervalo de consulta.
3. Si no hay un intervalo mayoritario que contenga por completo el intervalo de consulta, el valor correspondiente no puede ser el elemento mayoritario de este intervalo de consulta.
4. Cada elemento de la matriz de entrada está cubierto por intervalos de mayoría O (log n).

En otras palabras, el único propósito de los intervalos de mayoría es proporcionar O (log n) candidatos de elemento mayoritario para cualquier intervalo de consulta.

Este algoritmo utiliza las siguientes estructuras de datos :

1. Lista de posiciones para cada valor de la matriz de entrada ( map<Value, vector<Position>> ). Alternativamente, unordered_map puede usarse aquí para mejorar el rendimiento (pero necesitaremos extraer todas las claves y ordenarlas para que la estructura # 3 se complete en el orden correcto).
2. Lista de intervalos de la mayoría para cada valor ( vector<Interval> ).
3. Estructura de datos para manejar consultas ( vector<small_map<Value, Data>> ). Donde los Data contienen dos índices del vector apropiado de la estructura n. ° 1 que señala las posiciones siguientes / anteriores de los elementos con un valor dado. Actualización: gracias a @justhalf, es mejor almacenar en Data frecuencias acumuladas de los elementos con un valor dado. small_map puede implementarse como un vector ordenado de pares: el preprocesamiento agregará elementos ya en orden ordenado y la consulta usará small_map solo para la búsqueda lineal.

Preprocesamiento:

1. Escanee la matriz de entrada y empuje la posición actual al vector apropiado en la estructura n. ° 1.
2. Realice los pasos 3 .. 4 para cada vector en la estructura # 1.
3. Transforme la lista de posiciones en la lista de intervalos de la mayoría . Vea los detalles abajo.
4. Para cada índice de matriz de entrada cubierto por uno de los intervalos de la mayoría , inserte los datos en el elemento apropiado de la estructura n. ° 3: valor y posiciones de los elementos previos / siguientes con este valor (o la frecuencia acumulada de este valor ).

Consulta:

1. Si la longitud del intervalo de consulta es 1, devuelva el elemento correspondiente de la matriz fuente.
2. Para el punto de inicio del intervalo de consulta, obtenga el elemento correspondiente del vector de la 3ra estructura. Para cada elemento del mapa, realice el paso 3. Escanee todos los elementos del mapa correspondientes al punto final del intervalo de consulta en paralelo con este mapa para permitir O (1) complejidad para el paso 3 (en lugar de O (log log n)).
3. Si el mapa correspondiente al punto final del intervalo de consulta contiene un valor coincidente, calcule s3[stop][value].prev - s3[start][value].next + 1 . Si es mayor que la mitad del intervalo de consulta, devuelve el valor . Si se utilizan frecuencias acumuladas en lugar de los índices siguientes / anteriores, calcule s3[stop+1][value].freq - s3[start][value].freq en s3[stop+1][value].freq - s3[start][value].freq lugar.
4. Si no encontró nada en el paso 3, devuelva "Nothing".

La parte principal del algoritmo es obtener intervalos de la mayoría de la lista de posiciones:

1. Asigne un peso a cada posición en la lista: number_of_matching_values_to_the_left - number_of_nonmatching_values_to_the_left .
2. Filtre solo los pesos en orden estrictamente decreciente (ávidamente) a la matriz "prefijo": for (auto x: positions) if (x < prefix.back()) prefix.push_back(x); .
3. Filtre solo los pesos en orden estrictamente creciente (ávidamente, hacia atrás) a la matriz de "sufijo": reverse(positions); for (auto x: positions) if (x > suffix.back()) suffix.push_back(x); reverse(positions); for (auto x: positions) if (x > suffix.back()) suffix.push_back(x); .
4. Escanee los arreglos "prefijo" y "sufijo" juntos y encuentre los intervalos de cada elemento "prefijo" al lugar correspondiente en la matriz "sufijo" y de cada elemento "sufijo" al lugar correspondiente en la matriz "prefijo". (Si todos los pesos de los elementos "sufijo" son menores que el elemento "prefijo" dado o su posición no está a la derecha del mismo, no se genera intervalo; si no hay un elemento "sufijo" con exactamente el peso del elemento "prefijo" dado) , obtenga el elemento "sufijo" más cercano con mayor peso y amplíe el intervalo con esta diferencia de peso a la derecha).
5. Fusionar intervalos superpuestos.

Las propiedades 1 .. 3 para intervalos de la mayoría están garantizadas por este algoritmo. En cuanto a la propiedad n. ° 4, la única forma en que podría imaginarse cubrir algún elemento con el número máximo de intervalos de la mayoría es así: 11111111222233455666677777777 . Aquí el elemento 4 está cubierto por 2 * log n intervalos, por lo que esta propiedad parece estar satisfecha. Ver más prueba formal de esta propiedad al final de esta publicación.

Ejemplo:

Para la matriz de entrada "0 1 2 0 0 1 1 0" se generarían las siguientes listas de posiciones:

value  positions
    0  0 3 4 7
    1  1 5 6
    2  2

Las posiciones para el valor 0 obtendrán las siguientes propiedades:

weights:    0:1 3:0 4:1 7:0
prefix:     0:1 3:0          (strictly decreasing)
suffix:     4:1 7:0          (strictly increasing when scanning backwards)
intervals:  0->4 3->7 4->0 7->3
merged intervals: 0-7

Las posiciones para el valor 1 obtendrán las siguientes propiedades:

weights:    1:0  5:-2  6:-1
prefix:     1:0  5:-2
suffix:     1:0  6:-1
intervals:  1->none 5->6+1 6->5-1 1->none
merged intervals: 4-7

Estructura de datos de consulta:

positions value next prev
        0     0    0    x
     1..2     0    1    0
        3     0    1    1
        4     0    2    2
        4     1    1    x
        5     0    3    2
    ...

Consulta [0,4]:

prev[4][0]-next[0][0]+1=2-0+1=3
query size=5
3>2.5, returned result 0

Consulta [2,5]:

prev[5][0]-next[2][0]+1=2-1+1=2
query size=4
2=2, returned result "none"

Tenga en cuenta que no hay ningún intento de inspeccionar el elemento "1" porque su intervalo mayoritario no incluye ninguno de estos intervalos.

Prueba de propiedad # 4:

Los intervalos de mayoría se construyen de tal manera que estrictamente más de 1/3 de todos sus elementos tienen el valor correspondiente. Esta relación es más cercana a 1/3 para subcanales como any*(m-1) value*m any*m , por ejemplo, 01234444456789 .

Para hacer esta prueba más obvia, podríamos representar cada intervalo como un punto en 2D: cada punto de inicio posible representado por eje horizontal y cada punto final posible representado por eje vertical (ver diagrama a continuación).

Todos los intervalos válidos están ubicados en diagonal o más arriba. El rectángulo blanco representa todos los intervalos que cubren un elemento de matriz (representado como intervalo de tamaño de unidad en su esquina inferior derecha).

Cubramos este rectángulo blanco con cuadrados de tamaño 1, 2, 4, 8, 16, ... compartiendo la misma esquina inferior derecha. Esto divide el área blanca en áreas O (log n) similares a la amarilla (y un solo cuadrado de tamaño 1 que contiene un solo intervalo de tamaño 1 que es ignorado por este algoritmo).

Vamos a contar cuántos intervalos de la mayoría se pueden colocar en el área amarilla. Un intervalo (ubicado en la esquina diagonal más cercana) ocupa 1/4 de los elementos que pertenecen al intervalo en la esquina más alejada de la diagonal (y este intervalo más grande contiene todos los elementos que pertenecen a cualquier intervalo en el área amarilla). Esto significa que el intervalo más pequeño contiene estrictamente más de 1/12 valores disponibles para toda el área amarilla. Entonces, si tratamos de colocar 12 intervalos en el área amarilla, no tenemos suficientes elementos para diferentes valores . Entonces, el área amarilla no puede contener más de 11 intervalos de mayoría . Y el rectángulo blanco no puede contener más de 11 * log n intervalos de la mayoría . Prueba completa

11 * log n es sobreestimación. Como dije antes, es difícil imaginar más de 2 * log n intervalos de la mayoría cubriendo algún elemento. E incluso este valor es mucho mayor que el número promedio de intervalos principales de cobertura.

Implementación C ++ 11. ideone en ideone o aquí:

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
#include <random>

constexpr int SrcSize = 1000000;
constexpr int NQueries = 100000;

using src_vec_t = std::vector<int>;
using index_vec_t = std::vector<int>;
using weight_vec_t = std::vector<int>;
using pair_vec_t = std::vector<std::pair<int, int>>;
using index_map_t = std::map<int, index_vec_t>;
using interval_t = std::pair<int, int>;
using interval_vec_t = std::vector<interval_t>;
using small_map_t = std::vector<std::pair<int, int>>;
using query_vec_t = std::vector<small_map_t>;

constexpr int None = -1;
constexpr int Junk = -2;

src_vec_t generate_e()
{ // good query length = 3
    src_vec_t src;
    std::random_device rd;
    std::default_random_engine eng{rd()};
    auto exp = std::bind(std::exponential_distribution<>{0.4}, eng);

    for (int i = 0; i < SrcSize; ++i)
    {
        int x = exp();
        src.push_back(x);
        //std::cout << x << '' '';
    }

    return src;
}

src_vec_t generate_ep()
{ // good query length = 500
    src_vec_t src;
    std::random_device rd;
    std::default_random_engine eng{rd()};
    auto exp = std::bind(std::exponential_distribution<>{0.4}, eng);
    auto poisson = std::bind(std::poisson_distribution<int>{100}, eng);

    while (int(src.size()) < SrcSize)
    {
        int x = exp();
        int n = poisson();

        for (int i = 0; i < n; ++i)
        {
            src.push_back(x);
            //std::cout << x << '' '';
        }
    }

    return src;
}

src_vec_t generate()
{
    //return generate_e();
    return generate_ep();
}

int trivial(const src_vec_t& src, interval_t qi)
{
    int count = 0;
    int majorityElement = 0; // will be assigned before use for valid args

    for (int i = qi.first; i <= qi.second; ++i)
    {
        if (count == 0)
            majorityElement = src[i];

        if (src[i] == majorityElement) 
           ++count;
        else 
           --count;
    }

    count = 0;
    for (int i = qi.first; i <= qi.second; ++i)
    {
        if (src[i] == majorityElement)
            count++;
    }

    if (2 * count > qi.second + 1 - qi.first)
        return majorityElement;
    else
        return None;
}

index_map_t sort_ind(const src_vec_t& src)
{
    int ind = 0;
    index_map_t im;

    for (auto x: src)
        im[x].push_back(ind++);

    return im;
}

weight_vec_t get_weights(const index_vec_t& indexes)
{
    weight_vec_t weights;

    for (int i = 0; i != int(indexes.size()); ++i)
        weights.push_back(2 * i - indexes[i]);

    return weights;
}

pair_vec_t get_prefix(const index_vec_t& indexes, const weight_vec_t& weights)
{
    pair_vec_t prefix;

    for (int i = 0; i != int(indexes.size()); ++i)
        if (prefix.empty() || weights[i] < prefix.back().second)
            prefix.emplace_back(indexes[i], weights[i]);

    return prefix;
}

pair_vec_t get_suffix(const index_vec_t& indexes, const weight_vec_t& weights)
{
    pair_vec_t suffix;

    for (int i = indexes.size() - 1; i >= 0; --i)
        if (suffix.empty() || weights[i] > suffix.back().second)
            suffix.emplace_back(indexes[i], weights[i]);

    std::reverse(suffix.begin(), suffix.end());
    return suffix;
}

interval_vec_t get_intervals(const pair_vec_t& prefix, const pair_vec_t& suffix)
{
    interval_vec_t intervals;
    int prev_suffix_index = 0; // will be assigned before use for correct args
    int prev_suffix_weight = 0; // same assumptions

    for (int ind_pref = 0, ind_suff = 0; ind_pref != int(prefix.size());)
    {
        auto i_pref = prefix[ind_pref].first;
        auto w_pref = prefix[ind_pref].second;

        if (ind_suff != int(suffix.size()))
        {
            auto i_suff = suffix[ind_suff].first;
            auto w_suff = suffix[ind_suff].second;

            if (w_pref <= w_suff)
            {
                auto beg = std::max(0, i_pref + w_pref - w_suff);

                if (i_pref < i_suff)
                    intervals.emplace_back(beg, i_suff + 1);

                if (w_pref == w_suff)
                    ++ind_pref;

                ++ind_suff;
                prev_suffix_index = i_suff;
                prev_suffix_weight = w_suff;
                continue;
            }
        }

        // ind_suff out of bounds or w_pref > w_suff:
        auto end = prev_suffix_index + prev_suffix_weight - w_pref + 1;
        // end may be out-of-bounds; that''s OK if overflow is not possible
        intervals.emplace_back(i_pref, end);
        ++ind_pref;
    }

    return intervals;
}

interval_vec_t merge(const interval_vec_t& from)
{
    using endpoints_t = std::vector<std::pair<int, bool>>;
    endpoints_t ep(2 * from.size());

    std::transform(from.begin(), from.end(), ep.begin(),
                   [](interval_t x){ return std::make_pair(x.first, true); });

    std::transform(from.begin(), from.end(), ep.begin() + from.size(),
                   [](interval_t x){ return std::make_pair(x.second, false); });

    std::sort(ep.begin(), ep.end());

    interval_vec_t to;
    int start; // will be assigned before use for correct args
    int overlaps = 0;

    for (auto& x: ep)
    {
        if (x.second) // begin
        {
            if (overlaps++ == 0)
                start = x.first;
        }
        else // end
        {
            if (--overlaps == 0)
                to.emplace_back(start, x.first);
        }
    }

    return to;
}

interval_vec_t get_intervals(const index_vec_t& indexes)
{
    auto weights = get_weights(indexes);
    auto prefix = get_prefix(indexes, weights);
    auto suffix = get_suffix(indexes, weights);
    auto intervals = get_intervals(prefix, suffix);
    return merge(intervals);
}

void update_qv(
    query_vec_t& qv,
    int value,
    const interval_vec_t& intervals,
    const index_vec_t& iv)
{
    int iv_ind = 0;
    int qv_ind = 0;
    int accum = 0;

    for (auto& interval: intervals)
    {
        int i_begin = interval.first;
        int i_end = std::min<int>(interval.second, qv.size() - 1);

        while (iv[iv_ind] < i_begin)
        {
            ++accum;
            ++iv_ind;
        }

        qv_ind = std::max(qv_ind, i_begin);

        while (qv_ind <= i_end)
        {
            qv[qv_ind].emplace_back(value, accum);

            if (iv[iv_ind] == qv_ind)
            {
                ++accum;
                ++iv_ind;
            }

            ++qv_ind;
        }
    }
}

void print_preprocess_stat(const index_map_t& im, const query_vec_t& qv)
{
    double sum_coverage = 0.;
    int max_coverage = 0;

    for (auto& x: qv)
    {
        sum_coverage += x.size();
        max_coverage = std::max<int>(max_coverage, x.size());
    }

    std::cout << "             size = " << qv.size() - 1 << ''/n'';
    std::cout << "           values = " << im.size() << ''/n'';
    std::cout << "     max coverage = " << max_coverage << ''/n'';
    std::cout << "     avg coverage = " << sum_coverage / qv.size() << ''/n'';
}

query_vec_t preprocess(const src_vec_t& src)
{
    query_vec_t qv(src.size() + 1);
    auto im = sort_ind(src);

    for (auto& val: im)
    {
        auto intervals = get_intervals(val.second);
        update_qv(qv, val.first, intervals, val.second);
    }

    print_preprocess_stat(im, qv);
    return qv;
}

int do_query(const src_vec_t& src, const query_vec_t& qv, interval_t qi)
{
    if (qi.first == qi.second)
        return src[qi.first];

    auto b = qv[qi.first].begin();
    auto e = qv[qi.second + 1].begin();

    while (b != qv[qi.first].end() && e != qv[qi.second + 1].end())
    {
        if (b->first < e->first)
        {
            ++b;
        }
        else if (e->first < b->first)
        {
            ++e;
        }
        else // if (e->first == b->first)
        {
            // hope this doesn''t overflow
            if (2 * (e->second - b->second) > qi.second + 1 - qi.first)
                return b->first;

            ++b;
            ++e;
        }
    }

    return None;
}

int main()
{
    std::random_device rd;
    std::default_random_engine eng{rd()};
    auto poisson = std::bind(std::poisson_distribution<int>{500}, eng);
    int majority = 0;
    int nonzero = 0;
    int failed = 0;

    auto src = generate();
    auto qv = preprocess(src);

    for (int i = 0; i < NQueries; ++i)
    {
        int size = poisson();
        auto ud = std::uniform_int_distribution<int>(0, src.size() - size - 1);
        int start = ud(eng);
        int stop = start + size;
        auto res1 = do_query(src, qv, {start, stop});
        auto res2 = trivial(src, {start, stop});
        //std::cout << size << ": " << res1 << '' '' << res2 << ''/n'';

        if (res2 != res1)
            ++failed;

        if (res2 != None)
        {
            ++majority;

            if (res2 != 0)
                ++nonzero;
        }
    }

    std::cout << "majority elements = " << 100. * majority / NQueries << "%/n";
    std::cout << " nonzero elements = " << 100. * nonzero / NQueries << "%/n";
    std::cout << "          queries = " << NQueries << ''/n'';
    std::cout << "           failed = " << failed << ''/n'';

    return 0;
}

Trabajo relacionado:

Como se señala en otra respuesta a esta pregunta , hay otro trabajo donde este problema ya está resuelto: "Rango mayoritario en tiempo constante y espacio lineal" por S. Durocher, M. He, I Munro, PK Nicholson, M. Skala .

El algoritmo presentado en este documento tiene mejores complejidades asintóticas para el tiempo de consulta: O(1) lugar de O(log n) y para el espacio: O(n) lugar de O(n log n) .

Una mejor complejidad del espacio permite que este algoritmo procese conjuntos de datos más grandes (en comparación con el algoritmo propuesto en esta respuesta). Se necesita menos memoria para los datos preprocesados ​​y un patrón de acceso a datos más regular, lo más probable es que permita que este algoritmo preprocesa datos más rápidamente. Pero no es tan fácil con el tiempo de consulta ...

Supongamos que tenemos los datos de entrada más favorables al algoritmo del documento: n = 1000000000 (es difícil imaginar un sistema con más de 10 ... 30 gigabytes de memoria, en el año 2013).

El algoritmo propuesto en esta respuesta necesita procesar hasta 120 (o 2 límites de consulta * 2 * log n) elementos para cada consulta. Pero realiza operaciones muy simples, similares a la búsqueda lineal. Y accede de forma secuencial a dos áreas de memoria contiguas, por lo que es compatible con la memoria caché.

El algoritmo del documento debe realizar hasta 20 operaciones (o 2 límites de consulta * 5 candidatos * 2 niveles de árbol wavelet) para cada consulta. Esto es 6 veces menos Pero cada operación es más compleja. Cada consulta para la representación sucinta de los contadores de bits contiene una búsqueda lineal (lo que significa 20 búsquedas lineales en lugar de una). Lo peor de todo es que cada operación debe acceder a varias áreas de memoria independientes (a menos que el tamaño de la consulta y, por lo tanto, el tamaño cuádruple sea muy pequeño), por lo que la consulta es poco amigable con la caché. Lo que significa que cada consulta (mientras que es una operación de tiempo constante) es bastante lenta, probablemente más lenta que en el algoritmo propuesto aquí. Si disminuimos el tamaño de la matriz de entrada, aumentan las posibilidades de que el algoritmo aquí propuesto sea más rápido.

La desventaja práctica del algoritmo en el documento es el árbol wavelet y la implementación del contador de bits sucinto. Implementarlos desde cero puede consumir bastante tiempo. Usar una implementación preexistente no siempre es conveniente.

Answer 3

Puede usar MAX Heap, con frecuencia de número como factor decisivo para mantener la propiedad Max Heap, quise decir, por ejemplo, para la siguiente matriz de entrada

1 5 2 7 7 7 8 4 6 5

Heap would have all distinct elements with their frequency associated with them
    Element = 1  Frequency = 1,
    Element = 5  Frequency = 2,
    Element = 2  Frequency = 1,
    Element = 7  Frequency = 3,
    Element = 8  Frequency = 1,
    Element = 4  Frequency = 1,
    Element = 6  Frequency = 1

Como su montón MÁXIMO, Elemento 7 con frecuencia 3 estaría en el nivel raíz, solo compruebe si el rango de entrada contiene este elemento, si es así, esta es la respuesta si no, luego vaya al subárbol izquierdo o al subárbol derecho según el rango de entrada y realice mismos controles.

O (N) se requerirá solo una vez mientras se crea un montón, pero una vez creado, la búsqueda será eficiente.

Answer 4

Si tiene memoria ilimitada puede y rango de datos limitado (como short int) hágalo incluso en O (N) hora .

1. Vaya a través de la matriz y cuente el número de 1s, 2s, 3s, eta (número de entradas para cada valor que tenga en la matriz). Necesitará una matriz X adicional con elementos sizeof (YouType) para esto.
2. Ve a través de la matriz X y encuentra el máximo.

En total O (1) + O (N) operaciones.

También puede limitarse a sí mismo con la memoria O (N), si utiliza el mapa en lugar de la matriz X. Pero luego deberá encontrar el elemento en cada iteración en la etapa 1. Por lo tanto, necesitará O (N * log (N)) tiempo en total.

Answer 5

Editar: Lo siento, estaba resolviendo un problema diferente.

Ordene la matriz y construya una lista ordenada de pares (valor, number_of_occurrences) - es O(N log N). Empezando con

1 5 2 7 7 7 8 4 6

será

(1,1) (2,1) (4,1) (5,1) (6,1) (7,3) (8,1)

Además de esta matriz, crea un árbol binario con pares ( best_value_or_none , max_occurrences ). Se verá así:

(1,1) (2,1) (4,1) (5,1) (6,1) (7,3) (8,1)
   /   /       /   /       /  /       |
   (0,1)       (0,1)       (7,3)    (8,1)
        /     /                 /   /
         (0,1)                  (7,3)
              /                /
                     (7,3)

Esta estructura definitivamente tiene un nombre elegante, pero no la recuerdo :)

Desde aquí, es O(log N) para buscar el modo de cualquier intervalo. Cualquier intervalo puede dividirse en O(log N) intervalos precalculados; por ejemplo:

[4, 7] = [4, 5] + [6, 7]
f([4,5]) = (0,1)
f([6,7]) = (7,3)

y el resultado es (7,3).

Answer 6

el truco

Cuando busca un elemento de mayoría, puede descartar intervalos que no tienen un elemento de mayoría. Consulte Buscar el elemento de la mayoría en el conjunto . Esto te permite resolver esto de manera bastante simple.

preparación

En el momento de la preparación, de forma recursiva, siga dividiendo la matriz en dos mitades y almacene estos intervalos de matriz en un árbol binario. Para cada nodo, cuente la ocurrencia de cada elemento en el intervalo de la matriz. Necesita una estructura de datos que ofrezca O (1) inserciones y lecturas. Sugiero usar unsorted_multiset, que en promedio se comporta según sea necesario (pero las inserciones en el peor de los casos son lineales). También verifique si el intervalo tiene un elemento mayoritario y guárdelo si lo hace.

tiempo de ejecución

En el tiempo de ejecución, cuando se le pida que calcule el elemento de la mayoría para un rango, sumérjase en el árbol para calcular exactamente el conjunto de intervalos que cubre el rango especificado. Usa el truco para combinar estos intervalos.

Si tenemos el intervalo de matriz 7 5 5 7 7 7 , con el elemento de mayoría 7 , podemos dividir y descartar 5 5 7 7 ya que no tiene un elemento de mayoría. Efectivamente, los cinco han engullido dos de los sietes. Lo que queda es una matriz 7 7 o 2x7 . Llame a este número 2 el conteo mayoritario del elemento mayoritario 7 :

El recuento de la mayoría de un elemento de la mayoría de un intervalo de matriz es el recuento de ocurrencia del elemento de la mayoría menos la ocurrencia combinada de todos los demás elementos.

Use las siguientes reglas para combinar intervalos para encontrar el elemento potencial de la mayoría:

• Descartar los intervalos que no tienen un elemento mayoritario
• Combinar dos matrices con el mismo elemento de mayoría es fácil, simplemente suma los recuentos de la mayoría del elemento. 2x7 y 3x7 convierten en 5x7
• Al combinar dos matrices con diferentes elementos de la mayoría, gana el mayor recuento de la mayoría. Reste la cuenta de la mayoría más baja de la más alta para encontrar la cuenta de la mayoría resultante. 3x7 y 2x3 convierten en 1x7 .
• Si sus elementos de mayoría son diferentes pero tienen el mismo número de mayorías, ignore ambas matrices. 3x7 y 3x5 anulan mutuamente.

Cuando todos los intervalos han sido descartados o combinados, no tiene nada, en cuyo caso no hay un elemento mayoritario. O tiene un intervalo combinado que contiene un elemento de mayoría potencial. Busque y agregue los recuentos de ocurrencia de este elemento en todos los intervalos de matriz (también los descartados previamente) para verificar si realmente es el elemento mayoritario.

ejemplo

Para la matriz 1,1,1,2,2,3,3,2,2,2,3,2,2 , se obtiene el árbol (el elemento mayoritario de la cuenta x está entre paréntesis)

                        1,1,1,2,2,3,3,2,2,2,3,2,2    
                                  (1x2)
                      /                           /
             1,1,1,2,2,3,3                       2,2,2,3,2,2
                                                    (4x2)
            /              /                   /            /
        1,1,1,2           2,3,3            2,2,2             3,2,2
         (2x1)            (1x3)            (3x2)             (1x2)
        /     /          /    /            /    /            /    /
     1,1      1,2       2,3     3        2,2     2        3,2      2
    (1x1)                     (1x3)     (2x2)  (1x2)             (1x2)
    /   /     /  /     /   /            /  /             /   /
   1     1   1   2    2    3           2    2           3     2
(1x1) (1x1)(1x1)(1x2)(1x2)(1x3)       (1x2)(1x2)       (1x3) (1x2)     

El rango [5,10] (1-indexado) está cubierto por el conjunto de intervalos 2,3,3 (1x3), 2,2,2 (3x2). Ellos tienen diferentes elementos de la mayoría. Reste la mayoría de los conteos, te quedan 2x2. Entonces 2 es el elemento de la mayoría potencial. Buscar y sumar los recuentos de ocurrencia reales de 2 en las matrices: 1 + 3 = 4 de 6. 2 es el elemento de la mayoría.

El rango [1,10] está cubierto por el conjunto de intervalos 1,1,1,2,2,3,3 (sin elemento de mayoría) y 2,2,2 (3x2). Ignore el primer intervalo ya que no tiene un elemento mayoritario, por lo que 2 es el elemento de la mayoría potencial. Sume los recuentos de ocurrencia de 2 en todos los intervalos: 2 + 3 = 5 de 10. No hay elemento de mayoría.