Un algorithme peu encombrant pour trouver le plus grand sous-réseau équilibré?

Question

étant donné un tableau de 0 et de 1, trouvez un sous-tableau maximum tel que le nombre de zéros et de 1 soient égaux. Cela doit être fait en temps O (n) et en espace O (1).

J'ai un algo qui le fait en temps O (n) et en espace O (n). Il utilise un tableau sum de préfixes et exploite le fait que si le nombre de 0 et de 1 est identique, alors sumOfSubarray = lengthOfSubarray / 2

 #include<iostream>
#define M 15

using namespace std;

void getSum(int arr[],int prefixsum[],int size) {
    int i;
    prefixsum[0]=arr[0]=0;
    prefixsum[1]=arr[1];
    for (i=2;i<=size;i++) {
        prefixsum[i]=prefixsum[i-1]+arr[i];
    }
}

void find(int a[],int &start,int &end) {
    while(start < end) {
        int mid = (start +end )/2;
        if((end-start+1) == 2 * (a[end] - a[start-1]))
                break;
        if((end-start+1) > 2 * (a[end] - a[start-1])) {
            if(a[start]==0 && a[end]==1)
                    start++; else
                    end--;
        } else {
            if(a[start]==1 && a[end]==0)
                    start++; else
                    end--;
        }
    }
}

int main() {
    int size,arr[M],ps[M],start=1,end,width;
    ;
    cin>>size;
    arr[0]=0;
    end=size;
    for (int i=1;i<=size;i++)
            cin>>arr[i];
    getSum(arr,ps,size);
    find(ps,start,end);
    if(start!=end)
            cout<<(start-1)<<" "<<(end-1)<<endl; else cout<<"No soln\n";
    return 0;
}
 

Answer 1

Maintenant, mon algorithme est O(n) en temps et O(Dn) de l'espace où Dn est le nombre total de imblance dans la liste.

Cette solution ne doit pas modifier la liste.

soit D la différence de 1s et 0s trouvé dans la liste.

Tout d'abord, revenons en linearily par le biais de la liste et de calculer D, juste pour voir comment il fonctionne:

Je vais utiliser cette liste comme un exemple : l=1100111100001110

Element   D
null      0
1         1
1         2   <-
0         1
0         0
1         1
1         2
1         3
1         4
0         3
0         2
0         1
0         0
1         1
1         2
1         3
0         2   <-

Trouver le plus long équilibrée subarray est équivalent à trouver 2 éléments égaux en D qui sont le plus loin de l'appart. (dans cet exemple, les 2 2s marqué avec des flèches.)

La plus longue équilibré subarray est entre la première occurence de l'élément +1 et la dernière occurence de l'élément. (première flèche +1 et la dernière flèche : 00111100001110)

Remarque:

La plus longue subarray sera toujours entre 2 éléments de D qui sont entre [0,Dn] où Dn est le dernier élément de D. (Dn = 2 dans le exemple précédent) Dn est le total déséquilibre entre 1s et 0s dans les liste. (ou [Dn,0] si Dn est négatif)

Dans cet exemple, cela signifie que je n'ai pas besoin de "regarder" 3s ou 4s

La preuve:

Laissez-Dn > 0 .

Si il y a un subarray délimité par P (P > Dn). Puisque 0 < Dn < P, avant d'atteindre le premier élément de D, qui est égal à P, nous atteignons un élément égal à Dn. Ainsi, depuis le dernier élément de la liste est égal à Dn, il y a une plus longue subarray délimité par le Dns que celui délimité par le Ps.Et donc nous n'avons pas besoin de regarder Ps

P ne peut pas être inférieure à 0 pour les mêmes raisons

la preuve est la même pour Dn <0

Maintenant, nous allons travailler sur D, D n'est pas aléatoire, la différence entre les 2 éléments consécutifs est toujours 1 ou -1. Sna il est facile de bijection entre le D et la liste initiale. Donc j'ai 2 solutions à ce problème:

• la première est de garder une trace de la première et de la dernière apparition de chaque élément D qui sont entre 0 et Dn (cf la remarque).
• la deuxième est la transformation de la liste en D, et ensuite travailler sur D.

---

PREMIÈRE SOLUTION

Pour le moment je ne peut pas trouver une meilleure approche que la première:

Tout d'abord calculer Dn (en O(n)) . Dn=2

Deuxième au lieu de créer D, créer un dictionnaire dont les clés sont la valeur de D (entre [0 et Dn]) et la valeur de chacune de ces touches est un couple (a,b) où a est la première occurence de la clé et b le dernier.

Element   D DICTIONNARY
null      0 {0:(0,0)}
1         1 {0:(0,0) 1:(1,1)}
1         2 {0:(0,0) 1:(1,1) 2:(2,2)}
0         1 {0:(0,0) 1:(1,3) 2:(2,2)}
0         0 {0:(0,4) 1:(1,3) 2:(2,2)}
1         1 {0:(0,4) 1:(1,5) 2:(2,2)}
1         2 {0:(0,4) 1:(1,5) 2:(2,6)}
1         3 { 0:(0,4) 1:(1,5) 2:(2,6)}
1         4 {0:(0,4) 1:(1,5) 2:(2,6)}  
0         3{0:(0,4) 1:(1,5) 2:(2,6) }
0         2 {0:(0,4) 1:(1,5) 2:(2,9) }
0         1 {0:(0,4) 1:(1,10) 2:(2,9) } 
0         0 {0:(0,11) 1:(1,10) 2:(2,9) } 
1         1 {0:(0,11) 1:(1,12) 2:(2,9) } 
1         2 {0:(0,11) 1:(1,12) 2:(2,13)}
1         3 {0:(0,11) 1:(1,12) 2:(2,13)} 
0         2 {0:(0,11) 1:(1,12) 2:(2,15)} 

et vous avez choisi l'élément ayant la plus grande différence : 2:(2,15) et est l[3:15]=00111100001110 (avec l=1100111100001110).

Le temps de la complexité :

2 passes, la première à caclulate Dn, le second pour construire le dictionnaire. trouver le max dans le dictionnaire.

Total est O(n)

L'espace de la complexité:

l'élément en cours dans D : O(1) le dictionnaire O(Dn)

Je ne prends pas 3 et 4 dans le dictionnaire en raison de la remarque

La complexité est O(n) en temps et O(Dn) de l'espace (dans la moyenne des cas Dn << n).

Je suppose qu'il est peut-être une meilleure manière d'un dictionnaire de cette approche.

Toute suggestion est la bienvenue.

J'espère que ça aide

---

DEUXIÈME SOLUTION (JUSTE UNE IDÉE PAS LA VRAIE SOLUTION)

La deuxième façon de procéder serait de transformer votre liste dans D. (car il est facile de revenir en arrière à partir D pour la liste c'est ok). (O(n) en temps et O(1) de l'espace, depuis que je transforme la liste en place, même si il pourrait ne pas être un "valide" O(1) )

Puis, à partir de D, vous devez trouver les 2 égal élément qui sont le plus loin de l'appart.

il ressemble à trouver le cycle le plus long dans une liste liée, d'Une modification de Richard Brent algorithme peut retourner le cycle le plus long, mais je ne sais pas comment le faire, et il faudrait de O(n) en temps et O(1) de l'espace.

Une fois que vous trouver le plus long cycle, retour à la première de la liste et de l'imprimer.

Cet algorithme permettrait de prendre en O(n) en temps et O(1) l'espace de la complexité.

Answer 2

Approche différente, mais toujours O(n) le temps et la mémoire. Démarrer avec Neil à la suggestion de traiter 0 -1.

Notation: A[0, …, N-1] - votre tableau de taille N, f(0)=0, f(x)=A[x-1]+f(x-1) - une fonction

Si vous m'intrigue f, vous allez le voir, que ce que vous recherchez sont les points pour lesquels f(m)=f(n), m=n-2k où k-naturel positif. Plus précisément, seulement pour x tels que A[x]!=A[x+1] (et le dernier élément dans un tableau), vous devez vérifier si f(x) déjà eu lieu. Malheureusement, maintenant, je ne vois pas d'amélioration par rapport à avoir array B[-N+1…N-1] où ces informations seraient stockées.

Pour compléter ma pensée: B[x]=-1 initialement, B[x]=p lorsque p = min k: f(k)=x . Et l'algorithme est (double-vérifier, car je suis très fatigué):

fx = 0
B = new array[-N+1, …, N-1]
maxlen = 0
B[0]=0
for i=1…N-1 :
    fx = fx + A[i-1]
    if B[fx]==-1 :
        B[fx]=i
    else if ((i==N-1) or (A[i-1]!=A[i])) and (maxlen < i-B[fx]):
        We found that A[B[fx], …, i] is best than what we found so far
        maxlen = i-B[fx]

---

Edit: Deux lits-pensées (= compris pendant la pose dans le lit :P ):

1) Vous pourriez binaire de recherche, le résultat par la longueur de subarray, ce qui donnerait O(n log n) en temps et O(1) de la mémoire de l'algorithme. Nous allons utiliser la fonction g(x)=x - x mod 2 (en raison des sous-tableaux qui somme à 0 sont toujours de même longueur). Commencez par vérifier si l'ensemble des sommes à 0. Si oui, nous sommes de fait, sinon de continuer. Nous supposons maintenant 0 comme point de départ (nous savons qu'il y a subarray d'une telle longueur et de la "sommation à zéro de la propriété") et g(N-1) comme point de fin (nous le savons il n'y a pas subarray). Nous allons faire

    a = 0
    b = g(N-1)
    while a<b : 
        c = g((a+b)/2)
        check if there is such subarray in O(n) time
        if yes:
            a = c
        if no:
            b = c
    return the result: a (length of maximum subarray)

La vérification de subarray avec "résumant à zéro la propriété" d'une certaine longueur L est simple:

    a = 0
    b = L
    fa = fb = 0
    for i=0…L-1:
        fb = fb + A[i]
    while (fa != fb) and (b<N) :
        fa = fa + A[a]
        fb = fb + A[b]
        a = a + 1
        b = b + 1
    if b==N:
        not found
    found, starts at a and stops at b

2) ...pouvez-vous modifier le tableau d'entrée? Si oui et si O(1) de la mémoire signifie exactement, que vous utilisez pas d'espace supplémentaire (à l'exception de la constante nombre d'éléments), puis il suffit de stocker votre préfixe de la table de valeurs de votre tableau d'entrée. Pas plus d'espace utilisé (sauf pour certaines variables) :D

Et encore une fois, vérifiez mon algorithmes que je suis veeery fatigué et pourrait avez fait tout-en-un d'erreurs.

Answer 3

Comme Neil, je trouve utile de considérer l'alphabet {±1} au lieu de {0, 1}. Supposons sans perte de généralité qu'il y a au moins autant de +1 que -1s. L'algorithme suivant, qui utilise O(sqrt(n log n)) bits et s'exécute en temps O(n), est due à "A. F."

Remarque: cette solution ne triche pas, en supposant que l'entrée est modifiable et/ou a perdu bits. Comme de cette édition, cette solution est la seule posté qui est à la fois O(n) en temps et o(n) l'espace.

Une version plus facile, qui utilise O(n) bits, les ruisseaux de la matrice de préfixe des sommes et des marques de la première occurrence de chaque valeur. Il analyse ensuite vers l'arrière, en considérant pour chaque hauteur entre 0 et somme(arr) maximale subarray à cette hauteur. Certains pensaient révèle que l'optimum est entre ces (souvenez-vous de l'assomption). En Python:

sum = 0
min_so_far = 0
max_so_far = 0
is_first = [True] * (1 + len(arr))
for i, x in enumerate(arr):
    sum += x
    if sum < min_so_far:
        min_so_far = sum
    elif sum > max_so_far:
        max_so_far = sum
    else:
        is_first[1 + i] = False

sum_i = 0
i = 0
while sum_i != sum:
    sum_i += arr[i]
    i += 1
sum_j = sum
j = len(arr)
longest = j - i
for h in xrange(sum - 1, -1, -1):
    while sum_i != h or not is_first[i]:
        i -= 1
        sum_i -= arr[i]
    while sum_j != h:
        j -= 1
        sum_j -= arr[j]
    longest = max(longest, j - i)

L'astuce pour obtenir l'espace d'en bas vient de se rendre compte que nous sommes la numérisation is_first séquentiellement, mais dans l'ordre inverse par rapport à sa construction. Étant donné que la boucle des variables d'ajustement en O(log n) bits, nous allons calculer, au lieu de is_first, un point de contrôle de la boucle variables après chaque O(√(n log n)) étapes. Ce est O(n/√(n log n)) = O(√(n/log n)) des points de contrôle, pour un total de O(√(n log n)) bits. En redémarrant la boucle à partir d'un point de contrôle, on calcule à la demande de chaque O(√(n log n)) bits de la section de l' is_first.

(P. S.: il peut ou ne peut pas être de ma faute que l'énoncé du problème demande O(1) de l'espace. Sincèrement, je m'en excuse si c'est moi qui ai tiré un de Fermat et a suggéré que j'avais une solution à un problème beaucoup plus difficile que ce que je pensais.)

Answer 4

En effet, si votre algorithme est valide dans tous les cas (voir mon commentaire à votre question en notant quelques corrections à celle-ci), notez que le préfixe tableau est le seul obstacle à la permanence de la mémoire de l'objectif.

L'examen de la find fonction révèle que ce tableau peut être remplacé par deux nombres entiers, ce qui élimine la dépendance de la longueur de l'entrée et de la résolution de votre problème. Considérez les points suivants:

• Vous ne dépendent que de deux valeurs dans le préfixe de la matrice de dans la find fonction. Ce sont des a[start - 1] et a[end]. Oui, start et end changement, mais le fait mérite le tableau?
• Regardez la progression de votre boucle. À la fin, start est incrémenté ou end est décrémenté par une seule.
• Compte tenu de la déclaration précédente, si vous remplacez la valeur de a[start - 1] par un nombre entier, comment voulez-vous mettre à jour sa valeur? Mettre une autre manière, pour chaque passage dans la boucle qui modifie la valeur de start, que pourriez-vous faire pour mettre à jour l'entier en conséquence afin de refléter la nouvelle valeur de a[start - 1]?
• Ce procédé peut être répété avec a[end]?
• Si, en effet, les valeurs de a[start - 1] et a[end] peut être réfléchi à deux entiers, n'est-ce pas tout le préfixe de tableau n'ont plus d'utilité? Ne peut-il pas par conséquent être supprimée?

Sans avoir besoin de le préfixe de tableau et de stockage des dépendances sur la longueur de l'entrée enlevés, votre algorithme utilise une quantité constante de la mémoire pour atteindre son objectif, le rendant de ce fait O(n) en temps et O(1) de l'espace.

Je préfère vous résoudre ce problème vous-même basé sur les informations ci-dessus, ce sont les devoirs. Néanmoins, j'ai inclus une solution ci-dessous pour référence:

#include <iostream>
using namespace std;

void find( int *data, int &start, int &end )
{
    // reflects the prefix sum until start - 1
    int sumStart = 0;

    // reflects the prefix sum until end
    int sumEnd = 0;
    for( int i = start; i <= end; i++ )
        sumEnd += data[i];

    while( start < end )
    {
        int length = end - start + 1;
        int sum = 2 * ( sumEnd - sumStart );

        if( sum == length )
            break;
        else if( sum < length )
        {
            // sum needs to increase; get rid of the lower endpoint
            if( data[ start ] == 0 && data[ end ] == 1 )
            {
                // sumStart must be updated to reflect the new prefix sum
                sumStart += data[ start ];
                start++;
            }
            else
            {
                // sumEnd must be updated to reflect the new prefix sum
                sumEnd -= data[ end ];
                end--;
            }
        }
        else
        {
            // sum needs to decrease; get rid of the higher endpoint
            if( data[ start ] == 1 && data[ end ] == 0 )
            {
                // sumStart must be updated to reflect the new prefix sum
                sumStart += data[ start ];
                start++;
            }
            else
            {
                // sumEnd must be updated to reflect the new prefix sum
                sumEnd -= data[ end ];
                end--;
            }
        }
    }
}

int main() {
    int length;
    cin >> length;

    // get the data
    int data[length];
    for( int i = 0; i < length; i++ )
        cin >> data[i];

    // solve and print the solution
    int start = 0, end = length - 1;
    find( data, start, end );

    if( start == end )
        puts( "No soln" );
    else
        printf( "%d %d\n", start, end );

    return 0;
}

Answer 5

Cet algorithme est O(n) en temps et O(1) de l'espace. Il peut modifier le tableau source, mais il restaure toutes les informations de retour. Il n'est donc pas travailler avec const tableaux. Si cette énigme a plusieurs solutions, cet algorithme choisit la solution la plus proche de la matrice de départ. Ou il pourrait être modifié pour fournir toutes les solutions.

Algorithme

Variables:

• p1 - subarray commencer
• p2 - subarray fin

• d - différence de 1s et 0s dans les subarray

  1. Calculer d, si d==0, arrêter. Si d<0, inverser la matrice et après équilibré subarray est trouvé renverser en arrière.
  2. Alors qu' d > 0 avance p2: si l'élément du tableau est 1, juste décrémenter les deux p2 et d. Sinon, p2 devrait passer subarray de la forme 11*0où * est certains équilibré subarray. Pour faire de retour en arrière possible, 11*0? est changé en 0?*00 (où ? est la valeur du côté de la subarray). Ensuite, d est décrémenté.
  3. Stocker p1 et p2.
  4. Backtrack p2: si l'élément du tableau est 1, juste incrémenter p2. Sinon nous avons trouvé élément, modifié à l'étape 2. Annuler les changements et passer subarray de la forme 11*0.
  5. L'avance p1: si l'élément du tableau est 1, juste incrémenter p1. Sinon, p1 devrait passer subarray de la forme 0*11.
  6. Stocker p1 et p2, si p2 - p1 améliorée.
  7. Si p2 est à la fin du tableau, arrêter. Sinon, continuez avec l'étape 4.

Comment ça marche

L'algorithme parcourt toutes les positions possibles de l'équilibre subarray dans le tableau d'entrée. Pour chaque subarray position p1 et p2 sont conservés en tant que loin les uns des autres que possible, en fournissant localement plus longue subarray. Subarray avec le maximum de longueur est choisie entre toutes ces sous-réseaux.

Afin de déterminer la meilleure position pour p1, il est avancée à la première position où l'équilibre entre 1s et 0s est changé par un. (Étape 5).

Afin de déterminer la meilleure position pour p2, il est avancée à la dernière position où l'équilibre entre 1s et 0s est changé par un. Pour la rendre possible, l'étape 2 détecte toutes ces positions (à partir de la matrice de la fin de l') et modifie le tableau de telle manière, qu'il est possible de parcourir ces positions avec recherche linéaire. (Étape 4).

Lors de l'exécution de l'étape 2, deux conditions peuvent être remplies. Simple: lorsque la valeur " 1 " est trouvé; pointeur p2 est juste avancé à la valeur suivante, aucun traitement particulier n'est nécessaire. Mais lorsque la valeur " 0 " est trouvé, l'équilibre est d'aller dans la mauvaise direction, il est nécessaire de passer par plusieurs bits jusqu'à ce qu'un bon équilibre est trouvé. Tous ces morceaux sont d'aucun intérêt pour l'algorithme, s'arrêtant p2 il y aura de donner un équilibre subarray, qui est trop courte, ou un déséquilibré subarray. En conséquence, p2 devrait passer subarray de la forme 11*0 (de droite à gauche, * signifie que l'équilibre de toute subarray). Il n'y a aucune chance pour aller de la même façon dans l'autre sens. Mais il est possible de l'utilisation temporaire de certains bits de la répétition 11*0 afin de permettre les retours en arrière. Si nous modifions la première de '1' à '0', la seconde '1' pour la valeur du côté de l'extrême droite '0', et clairement la valeur du côté de l'extrême droite '0': 11*0? -> 0?*00, puis, nous avons la possibilité de (première) notez le modèle sur le chemin du retour, car il commence avec '0', et (ii) de trouver la prochaine position pour p2.

Le code C++:

#include <cstddef>
#include <bitset>

static const size_t N = 270;

void findLargestBalanced(std::bitset<N>& a, size_t& p1s, size_t& p2s)
{
    // Step 1
    size_t p1 = 0;
    size_t p2 = N;
    int d = 2 * a.count() - N;
    bool flip = false;

    if (d == 0) {
        p1s = 0;
        p2s = N;
        return;
    }

    if (d < 0) {
        flip = true;
        d = -d;
        a.flip();
    }

    // Step 2
    bool next = true;
    while (d > 0) {
        if (p2 < N) {
            next = a[p2];
        }

        --d;
        --p2;

        if (a[p2] == false) {
            if (p2+1 < N) {
                a[p2+1] = false;
            }

            int dd = 2;
            while (dd > 0) {
                dd += (a[--p2]? -1: 1);
            }

            a[p2+1] = next;
            a[p2] = false;
        }
    }

    // Step 3
    p2s = p2;
    p1s = p1;

    do {
        // Step 4
        if (a[p2] == false) {
            a[p2++] = true;
            bool nextToRestore = a[p2];
            a[p2++] = true;

            int dd = 2;
            while (dd > 0 && p2 < N) {
                dd += (a[p2++]? 1: -1);
            }

            if (dd == 0) {
                a[--p2] = nextToRestore;
            }
        }
        else {
            ++p2;
        }

        // Step 5
        if (a[p1++] == false) {
            int dd = 2;
            while (dd > 0) {
                dd += (a[p1++]? -1: 1);
            }
        }

        // Step 6
        if (p2 - p1 > p2s - p1s) {
            p2s = p2;
            p1s = p1;
        }
    } while (p2 < N);

    if (flip) {
        a.flip();
    }
}