Cara tercepat untuk menemukan produk minimal 2 elemen array yang mengandung 200000+ elemen

13

Saya memiliki sebuah array a[n]. Nomor ntersebut dimasukkan oleh kami. Saya perlu mencari produk minimal a[i]dan a[j]jika:

1) abs(i - j) > k

2) a[i] * a[j]diminimalkan

Inilah solusi saya (sangat naif):

#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;
}

Tapi saya ingin tahu apakah ada cara yang lebih cepat untuk menemukan produk minimal dengan jarak?

Mouvre
sumber
7
Mengapa saya tidak memasukkan # bits / stdc ++. H>? dan C ++ hanya menyediakan Array Panjang Variabel dengan ekstensi kompiler. Kenapa kamu tidak menggunakan std::vector? @Scheff - pengurutan akan menghancurkan hubungan "jarak" yang asli.
David C. Rankin
3
Setidaknya cek if (i!=j) if (abs(i - j) > k)bisa dihilangkan. Hanya mulai loop batin di i + k + 1: for (ll j = i + k + 1; j < n; ++j). Pemeriksaan dengan firstdapat dihilangkan juga jika mndiinisialisasi sebelumnya misalnya dengan mn = a[0] * a[k + 1];. (Mungkin, kharus diperiksa pada nawalnya untuk membuat bukti-peluru ini.) Tapi itu masih O (N²). Ini harus bisa dilakukan lebih cepat ...
Scheff
2
@PaulMcKenzie Tolong tunjukkan satu permintaan dengan tidak kurang dari dua klik yang berguna di antara sepuluh hit pertama untuk produk minimal dengan jarak indeks (atau maksimal).
greybeard
1
@PaulMcKenzie "Mungkin ada ratusan, jika tidak ribuan tautan URL yang menunjukkan jawaban untuk pertanyaan ini." - silakan bagikan setidaknya tiga dari URL ini.
גלעד ברקן
2
Dari mana datangnya pertanyaan ini? Itu tidak terdengar seperti sesuatu yang hanya terbuat dari udara tipis. Saya tidak akan terkejut jika itu berasal dari salah satu situs "hakim online" itu. Jika demikian, di situs-situs itu mungkin diskusi panjang tentang penyelesaian masalah, jika bukan solusi lengkap.
PaulMcKenzie

Jawaban:

12

Dengan asumsi setidaknya ada sepasang elemen yang memenuhi kondisi dan tidak ada perkalian dua elemen di dalamnya meluap, ini dapat dilakukan dalam Theta(n-k)waktu dan Theta(1)ruang terburuk-dan-kasus terbaik, dengan sesuatu seperti ini:

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;

Ini optimal dalam hal kompleksitas kasus terburuk asimptotik untuk waktu dan ruang karena produk yang optimal mungkin a[0]dengan salah satu n-(k+1)elemen dalam jarak setidaknya k+1, sehingga setidaknya n-(k+1)bilangan bulat perlu dibaca oleh algoritma yang memecahkan masalah.


Gagasan di balik algoritma adalah sebagai berikut:

Produk optimal menggunakan dua elemen a, anggap ini a[r]dan a[s]. Tanpa kehilangan s > rsifat umum kita dapat mengasumsikan bahwa karena produk tersebut bersifat komutatif.

Karena pembatasan abs(s-r) > kini menyiratkan bahwa s >= k+1. Sekarang sbisa masing-masing indeks memenuhi kondisi ini, jadi kami beralih pada indeks ini. Itu adalah iterasi idi atas dalam kode yang ditampilkan, tetapi digeser oleh k+1untuk kenyamanan (tidak terlalu penting). Untuk setiap iterasi kita perlu menemukan produk optimal yang melibatkan i+k+1sebagai indeks terbesar dan membandingkannya dengan tebakan terbaik sebelumnya.

Kemungkinan indeks untuk dipasangkan i+k+1adalah semua indeks lebih kecil atau sama ikarena persyaratan jarak. Kita perlu mengulangi semua ini juga, tetapi itu tidak perlu karena minimum a[i+k+1]*a[j]kelebihan jpada saat iyang sama adalah min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))karena monotonitas produk (mengambil minimum sehubungan dengan minimum dan maksimum atas a[j]akun untuk dua kemungkinan) tanda-tanda a[i+k+1]atau ekuivalen dua kemungkinan arah monotonisitas.)

Karena himpunan a[j]nilai yang kami optimalkan di sini adalah adil {a[0], ..., a[i]}, yang hanya tumbuh dengan satu elemen ( a[i]) di setiap iterasi i, kami hanya dapat melacak max(a[j])dan min(a[j])dengan variabel tunggal dengan memutakhirkannya jika a[i]lebih besar atau lebih kecil dari nilai optimal sebelumnya. Ini dilakukan dengan back_maxdan back_mindalam contoh kode.

Langkah pertama dari iterasi ( i=0) dilewati dalam loop dan sebagai gantinya dilakukan sebagai inisialisasi variabel.

kenari
sumber
3
@ Greybeard Saya tidak perlu menyimpannya, karena satu-satunya kandidat yang memungkinkan untuk produk yang optimal a[i+k+1]adalah minimum dan maksimum.
kenari
dapatkah Anda menjelaskan mengapa algoritme berfungsi dalam jawaban Anda?
MinaHany
6

Tidak yakin tentang yang tercepat .

Untuk masalah yang lebih sederhana tanpa i <j - k , produk minimal adalah di antara produk pasangan dari dua elemen terkecil dan terbesar.

Jadi, (yang berikut ini terlalu rumit, lihat jawaban walnut )
(• menolak jika k ≤ n
  • menginisialisasi minProduk ke [0] * a [k + 1])

  • pertahankan dua struktur data minmax dinamis tetap upToI dan beyondIplusK
    dimulai dengan {} dan {a [ j ] | kj }
  • untuk setiap i dari 0 hingga n - k - 1
    • tambahkan [ i ] ke upToI
    • menghapus [ i + k ] dari beyondIplusK
    • periksa produk minimal baru di antara
      min ( upToI ) × min (di luarIplusK ), min ( upToI ) × maks (di luarIplusK ),
      maks ( upToI ) × min (di luarIplusK ) dan maks ( upToI ) × maks (di luarIplusK )
greybeard
sumber
Ini harus menjadi yang tercepat, setidaknya dari segi kompleksitas. Ini adalah O (n) waktu dan penyimpanan.
smttsp
solusi asli memiliki kompleksitas O (N ** 2), bagaimana Anda memperkirakan kompleksitas solusi Anda?
lenik
O (nlogn) waktu, O (n) ruang (untuk implementasi
minmax yang
@orangtua. Mengapa Anda perlu n * logn waktu. Mengapa tidak hanya menjaga 4 * n array berisi minUpto, maxUpto, minBeyond, maxBeyond(Anda dapat membuat dalam dua iterasi)? Kemudian, dalam iterasi ketiga, untuk setiap indeks, temukan perkalian min yang mungkin.
smttsp
(@smttsp Itu akan menjadi langkah alternatif ke arah solusi walnut .)
greybeard
4

Untuk "magnitudo minimum"

Temukan 2 elemen "magnitudo terkecil", lalu (setelah Anda menemukan dua nol atau mencari seluruh array), gandakanlah.

Untuk "nilai terendah" tanpa abs(i - j) > kbagian

Ada 3 kemungkinan:

  • dua angka negatif tertinggi (terkecil terkecil)

  • dua angka non-negatif terendah (terkecil terkecil)

  • angka negatif terendah (terbesar) dan tertinggi (terbesar terbesar) non-negatif

Anda bisa mencari semua 6 nilai dan mencari tahu produk dan mana yang terbaik pada akhirnya.

Namun; segera setelah Anda melihat nol Anda tahu Anda tidak perlu tahu lagi tentang 2 kemungkinan pertama; dan segera setelah Anda melihat satu angka negatif dan satu angka non-negatif Anda tahu bahwa Anda hanya peduli pada kemungkinan ketiga.

Ini mengarah ke mesin negara terbatas dengan 3 negara - "peduli tentang semua 3 kemungkinan", "jawabannya nol kecuali angka negatif terlihat" dan "hanya peduli tentang kemungkinan terakhir". Ini dapat diimplementasikan sebagai satu set 3 loop, di mana 2 loop melompat ke ( goto) di tengah loop lain ketika keadaan (dari mesin keadaan terbatas) berubah.

Secara khusus, ini mungkin terlihat seperti samar-samar (belum diuji):

   // 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;

Untuk "nilai terendah" dengan abs(i - j) > kbagian itu

Dalam hal ini Anda masih memiliki 3 kemungkinan; dan bisa membuatnya bekerja dengan pendekatan yang sama "3 loop dengan mesin negara yang terbatas" tetapi terlalu berantakan / jelek. Untuk kasus ini, alternatif yang lebih baik kemungkinan untuk melakukan pra-pemindaian array untuk menentukan apakah ada nol dan apakah semuanya negatif atau semuanya positif; sehingga setelah pra-pemindaian Anda dapat mengetahui jawabannya adalah nol atau pilih satu loop yang dirancang untuk kemungkinan tertentu saja.

Brendan
sumber
1
Di mana akun ini untuk k batas bawah pada perbedaan indeks?
greybeard
1
@ Greybeard: Tidak (saya melewatkan bagian itu) - kode perlu dimodifikasi untuk memperhitungkannya.
Brendan
Mengapa Anda membutuhkan dua nol?
TrentP
@RentP: Argh - Anda benar. Satu nol sudah cukup untuk mengetahui jawabannya adalah 0 atau angka negatif.
Brendan