A maneira mais rápida de encontrar um produto mínimo de 2 elementos de matriz contendo mais de 200000 elementos

13

Eu tenho uma matriz a[n]. O número né inserido por nós. Preciso encontrar o produto mínimo a[i]e a[j]se:

1) abs(i - j) > k

2) a[i] * a[j]é minimizado

Aqui está a minha solução (muito ingênua):

#include <iostream>
using namespace std;
#define ll long long
int main() {
    ll n,k; cin >> n >> k;

    ll a[n]; for(ll i=0;i<n;i++) cin >> a[i];

    ll mn; bool first = true;

    for(ll i=0;i<n;i++) {
        for(ll j=0;j<n;j++) {
            if(i!=j)
            if(abs(i-j) > k) {
                if(first) {
                    mn = a[i]*a[j];
                    first = false;
                } else if(a[i]*a[j] < mn) mn = a[i]*a[j];
            }
        }
    }
    cout << mn << endl;
}

Mas quero saber se existe alguma maneira mais rápida de encontrar um produto mínimo com distância?

Mouvre
fonte
7
Por que não devo # incluir <bits / stdc ++. H>? e C ++ fornecem apenas uma matriz de comprimento variável por extensão do compilador. Por que você não está usando std::vector? @Scheff - a classificação destruiria os relacionamentos originais de "distância".
David C. Rankin
3
Pelo menos o cheque if (i!=j) if (abs(i - j) > k)pode ser eliminado. Apenas iniciar o ciclo interior em i + k + 1: for (ll j = i + k + 1; j < n; ++j). A verificação com também firstpode ser eliminada se mnfor inicializada anteriormente, por exemplo, com mn = a[0] * a[k + 1];. (Talvez, kdeva ser verificado ninicialmente para fazer essa prova de bala.) Mas ainda é O (N²). Isso deve ser possível mais rápido ...
Scheff 12/01
2
@PaulMcKenzie Mostre uma consulta com pelo menos dois hits úteis entre os dez primeiros para um produto mínimo com distância do índice (ou máximo).
greybeard 12/01
11
@PaulMcKenzie "Provavelmente existem centenas, senão milhares de links de URL que mostram respostas para esta pergunta." - compartilhe pelo menos três desses URLs.
גלעד ברקן 12/01
2
De onde veio essa pergunta? Não parece algo inventado do nada. Eu não ficaria surpreso se fosse de um desses sites de "juízes on-line". Nesse caso, nesses sites provavelmente há longas discussões sobre a solução do problema, se não soluções completas.
PaulMcKenzie 12/01

Respostas:

12

Supondo que haja pelo menos um par de elementos que satisfaça as condições e nenhuma multiplicação de dois elementos nele exceda, isso pode ser feito no Theta(n-k)tempo e no Theta(1)espaço, na pior e na melhor das hipóteses, com algo assim:

auto back_max = a[0];
auto back_min = a[0];
auto best = a[0]*a[k+1];

for(std::size_t i=1; i<n-(k+1); ++i) {
    back_max = std::max(back_max, a[i]);
    back_min = std::min(back_min, a[i]);
    best = std::min(best, std::min(a[i+k+1]*back_max, a[i+k+1]*back_min));
}

return best;

Isso é ideal em termos de complexidade assintótica de pior caso, tanto no tempo quanto no espaço, porque o produto ideal pode estar a[0]com qualquer um dos n-(k+1)elementos à distância, pelo menos k+1, portanto, pelo menos, n-(k+1)números inteiros precisam ser lidos por qualquer algoritmo que resolva o problema.


A ideia por trás do algoritmo é a seguinte:

O produto ideal usa dois elementos de a, assuma que são a[r]e a[s]. Sem perda de generalidade, podemos assumir que, s > ruma vez que o produto é comutativo.

Devido à restrição, abs(s-r) > kisso implica que s >= k+1. Agora, scada um dos índices pode satisfazer essa condição, portanto, iteramos sobre esses índices. Essa é a iteração ido código mostrado, mas é alterada por k+1conveniência (realmente não importa). Para cada iteração, precisamos encontrar o produto ideal envolvendo i+k+1o maior índice e compará-lo com a melhor estimativa anterior.

Os possíveis índices para parear i+k+1são todos menores ou iguais idevido ao requisito de distância. Também precisaríamos iterar sobre tudo isso, mas isso é desnecessário porque o mínimo de a[i+k+1]*a[j]excesso jno fixo ié igual a min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))devido à monotonicidade do produto (levando o mínimo em relação às a[j]contas de excesso e de mínimo e máximo para as duas possíveis sinais a[i+k+1]ou equivalentes as duas direções possíveis da monotonicidade.)

Como o conjunto de a[j]valores sobre os quais otimizamos aqui é justo {a[0], ..., a[i]}, que simplesmente cresce em um elemento ( a[i]) em cada iteração i, podemos simplesmente acompanhar max(a[j])e min(a[j])com variáveis ​​únicas atualizando-as se a[i]for maior ou menor que os valores ideais anteriores. Isso é feito com back_maxe back_minno exemplo de código.

A primeira etapa da iteração ( i=0) é pulada no loop e executada como inicialização das variáveis.

noz
fonte
3
@greybeard Eu não preciso mantê-los por perto, porque os únicos candidatos possíveis para um produto ideal a[i+k+1]são o mínimo e o máximo.
noz
você poderia explicar por que o algoritmo funciona na sua resposta?
MinaHany 12/01
6

Não tenho certeza sobre o mais rápido .

Para o problema mais simples sem i <j - k , o produto mínimo está entre os produtos dos pares dos dois menores e maiores elementos.

Portanto, (o seguinte é muito complicado, veja a resposta da noz )
(• rejeite se k ≤ n
  • inicialize minProduct para a [0] * a [k + 1])

  • mantenha duas estruturas dinâmicas minmax de dados upToI e beyondIplusK
    começando com {} e {a [ j ] | kj }
  • para cada i de 0 a n - k - 1
    • adicione um [ i ] ao upToI
    • remover um [ i + k ] do beyondIplusK
    • verifique se há novo produto mínimo entre
      min ( upToI ) × min ( beyondIplusK ), min ( upToI ) × max ( beyondIplusK ),
      max ( upToI ) × min ( beyondIplusK ) e max ( upToI ) × max ( beyondIplusK )
greybeard
fonte
Esse deve ser o mais rápido, pelo menos em termos de complexidade. É O (n) tempo e armazenamento.
smttsp 12/01
a solução original tem a complexidade O (N ** 2), como você estima a complexidade da sua solução?
lenik 12/01
O (nlogn) time, O (n) space (para implementações minmax adequadas)
greybeard
@greybeard. Por que você precisa de tempo n * logn. Por que não simplesmente manter uma matriz n * 4, que contém minUpto, maxUpto, minBeyond, maxBeyond(Você pode criar em duas iterações)? Em seguida, na terceira iteração, para cada índice, encontre o mínimo possível de multiplicação.
smttsp 12/01
(@smttsp Isso seria um passo alternativo na direção da solução da noz .)
greybeard
4

Para "magnitude mínima"

Encontre os 2 elementos "menor magnitude" e depois (depois de encontrar dois zeros ou pesquisar em toda a matriz), multiplique-os.

Para "valor mais baixo" sem a abs(i - j) > kpeça

Existem 3 possibilidades:

  • os dois números negativos mais altos (menor magnitude)

  • os dois números não negativos de menor magnitude (menor magnitude)

  • o número negativo mais baixo (maior magnitude) e o número não negativo mais alto (maior magnitude)

Você pode procurar todos os 6 valores e descobrir os produtos e qual é o melhor no final.

Contudo; assim que você vê um zero, sabe que não precisa mais saber sobre as duas primeiras possibilidades; e assim que vir um número negativo e um número não negativo, você saberá que só se importa com a terceira possibilidade.

Isso leva a uma máquina de estados finitos com 3 estados - "cuidado com todas as 3 possibilidades", "a resposta é zero, a menos que um número negativo seja visto" e "apenas se preocupa com a última possibilidade". Isso pode ser implementado como um conjunto de 3 loops, onde 2 dos loops saltam para ( goto) o meio de outro loop quando o estado (da máquina de estados finitos) muda.

Especificamente, pode parecer algo vagamente semelhante (não testado):

   // It could be any possibility

   for(ll i=0;i<n;i++) {
       if(a[i] >= 0) {
            if(a[i] < lowestNonNegative1) {
                lowestNonNegative2 = lowestNonNegative1;
                lowestNonNegative1 = a[i];
            }
            if(lowestNonNegative2 == 0) {
                goto state2;
            }
       } else {
            if(a[i] > highestNegative1) {
                highestNegative2 = highestNegative1;
                highestNegative1= a[i];
            }
            if(lowestNonNegative1 < LONG_MAX) {
                goto state3;
            }
       }
   }
   if(lowestNonNegative2 * lowestNonNegative1 < highestNegative2 * highestNegative1) {
       cout << lowestNonNegative2 * lowestNonNegative1;
   } else {
       cout << highestNegative2 * highestNegative1;
   }
   return;

   // It will be zero, or a negative and a non-negative

   for(ll i=0;i<n;i++) {
state2:
       if(a[i] < 0) {
           goto state3;
       }
   }
   cout << "0";
   return;

   // It will be a negative and a non-negative

   for(ll i=0;i<n;i++) {
state3:
       if(a[i] < lowestNegative) {
           lowestNegative = a[i];
       } else if(a[i] > highestNonNegative) {
           highestNonNegative = a[i];
       }
    }
    cout << lowestNegative * highestNonNegative;
    return;

Para "valor mais baixo" com a abs(i - j) > kparte

Nesse caso, você ainda tem as 3 possibilidades; e poderia fazê-lo funcionar com a mesma abordagem "3 loops com máquina de estados finitos", mas fica muito confuso / feio. Nesse caso, é provável que uma alternativa melhor faça uma varredura prévia da matriz para determinar se há zeros e se todos são negativos ou positivos; para que, após a pré-digitalização, você saiba que a resposta é zero ou selecione um loop projetado apenas para a possibilidade específica.

Brendan
fonte
11
Onde isso explica o limite inferior k na diferença de índice?
greybeard 12/01
11
@greybeard: Não (eu perdi essa parte) - o código precisaria ser modificado para levar isso em conta.
Brendan
Por que você precisaria de dois zeros?
TrentP 12/01
@TrentP: Argh - você está certo. Um zero é suficiente para saber que a resposta é 0 ou um número negativo.
Brendan