Você deu um conjunto de intervalos como {2,7}, {3,8}, {9,11}, {-4, -1}, etc. A questão é encontrar o k "min min a partir desses intervalos.
Além disso, as duplicatas são contadas duas vezes. Por exemplo, se os intervalos forem {1,4} e {2,6} ek = 3, então a resposta é 2, porque se achatarmos os intervalos e classificarmos os mesclar, obteremos a sequência
1,2,2,3,3,4,4,5,6
Onde 3 min é 3.
Pode haver muitas maneiras de resolver esse problema. No entanto, estou lutando para encontrar aquele com complexidade mínima de tempo / espaço.
Respostas:
3 para resposta № 1- Flat os intervalos.
- Classifique a sequência achatada.
- Iterar sobre a sequência classificada, até encontrar o
k-ésimo elemento enquanto ignora valores duplicados.
Agora vamos fazer algumas análises, onde definimos N o número total de números presentes nos seus intervalos e M o número médio de valores duplicados que um número terá (será 1 para uma sequência de achatamento exclusiva).
Complexidade Espacial:
EM)
onde você poderia fazer melhor, se você tem muitos elementos duplicados, iterando sobre a seqüência planificada, enquanto descarta os elementos duplicados.
Complexidade do Tempo:
O (k * M + NlogN)
- Achatamento leva O (N)
- Ordenar leva O (NlogN)
- Iteração leva O (k * M)