Abfrage an all benachbarten Subarray der Größe K

Question

Lassen Sie sich auf ein Array der Größe B[1:K] eine Operation definieren K das heißt die Anzahl der Elemente in dem Subarray zählt B[2:K] welche als B[1] kleiner sind.

Jetzt habe ich ein Array A[1:N] der Größe N und mein Ziel ist es, die obige Operation auf allen zusammenhängenden Subarrays der Größe K durchzuführen.

Beispiel

A = [4, 3, 6, 2, 1] and K = 3 Es gibt 3 angrenzenden Sub-Array von Größe 3.

1. B = [4, 3, 6]count = 1[(3 < 4)]
2. B = [3, 6, 2]count = 1[(2 < 3)]
3. B = [6, 2, 1]count = 2[(2 < 6), (1 < 6)]

Zeitkomplexität des Brute-Force-Ansatzes wird O((N-K+1)*K) sein, da die obige Operation auf einem angrenzenden Sub-Arrays der Größe der Durchführung K ist O(K).

Ich kann es in Nlog(M) effizient also tun, wenn ich eine Datenstruktur entwerfen , die folgenden Eigenschaften

1. Insertion in log(M)
2. Deletion in log(M)
3. Count Anzahl der Elemente kleiner als X hat in log(M)

Ich bin C++ Benutzer und ich glaube nicht, dass es eine Datenstruktur gibt, die alle genannten Anforderungen erfüllt. Gibt es andere Möglichkeiten zur Verbesserung? Bitte helfen Sie.

Answer 1

Hilft das?

#include <iostream> 
#include <cstdio> 
#include <set> 
using namespace std; 
int bit[100005]={0}; 
// using BIT since numbers can repeat and set won't work 
void update(int idx, int val, int n){ 
    while(idx < n){ 
     bit[idx] += val; 
     idx += (idx & -idx); 
    } 
} 
int get(int idx){ 
    int ret = 0; 
    while(idx > 0){ 
     ret += bit[idx]; 
     idx -= (idx & -idx); 
    } 
    return ret; 
} 
int main() { 
    int n, a[100005] = {0}, i, ans=0, k, maxx = -1; 
    scanf("%d%d", &n, &k); 
    for(i=0; i<n; i++){ 
     scanf("%d", &a[i]); 
     if(maxx < a[i]){ 
      maxx = a[i]; 
     } 
    } 
    maxx++; 
    for(i=0;i<n;i++){ 
     a[i] = maxx - a[i]; 
    } 

    // now the problem becomes the opposite of what it initially was 
    // now a[i] would contribute to ans if we can find an element a[j] where a[j] < a[i] and (i-j)<=k 

    for(i=0;i<n;i++){ 
     if(i-k>=0){ 
      // remove i-k'th element from the BIT since it doesn't contribute 
      update(a[i-k], -1, maxx); 
     } 
     if(i >= k-1){ 
      // add how a[i] is gonna contribute to the final answer, it would be the number of elements less than a[i] 
      ans += get(a[i]); 
     } 
     // add a[i] to the BIT 
     update(a[i], 1, maxx); 
    } 
    printf("%d\n", ans); 
    return 0; 
} 

Answer 2

Sie möchten vielleicht weniger mit zusätzlichen Betrieb des Zählens Elemente verwenden eingestellt als k. Dies kann als binärer Suchbaum implementiert werden (klassische Set-Implementierung) mit zusätzlicher Statistik in jedem Knoten (grundsätzlich Größe des Knotens im Baum).

Weitere Details hier: https://stackoverflow.com/a/15321444/1391392 Und einige Implementierung hier: https://sourceforge.net/projects/orderstatistics/

Andere Option, die mehr straighforward aussehen könnte, ist skiplists zu verwenden. https://en.wikipedia.org/wiki/Skip_list