Peut-on calculer cela en moins de O (n * n) ... (nlogn ou n)

https://stackoverflow.com/questions/3659506

01-10-2019
|

Question

Ceci est une question me posée par un MNC très célèbre. La question est la suivante ...

Input un tableau 2D N * N de 0 et de 1. Si A (i, j) = 1, alors toutes les valeurs correspondant à la i-ième ligne et la j-ième colonne vont être 1. S'il y a un 1 déjà, il reste sous forme de 1.

Par exemple, si nous avons le tableau

nous devrions obtenir la sortie comme

La matrice d'entrée est faible densité de population.

Est-ce possible en moins de O (N ^ 2)?

Aucun espace supplémentaire est prévu était une autre condition. Je voudrais savoir s'il y a un moyen d'atteindre la complexité en utilisant un espace <= O (N).

P.S: Je ne répond pas besoin qui me donnent une complexité de O (N * N). Ce n'est pas un problème de devoirs. J'ai essayé beaucoup et ne pouvait pas obtenir une solution appropriée et pensé que je pourrais obtenir quelques idées here.Leave l'impression de côté pour la complexité

Mon idée approximative était peut-être éliminer dynamiquement le nombre d'éléments traversés en les limitant à environ 2N ou plus. Mais je ne pouvais pas avoir une idée correcte.

La solution 7

les gars Hii,

grâce au commentaire de MB14 je pense que je pourrais l'obtenir résolu en moins de O (N n) ... Le pire serait de prendre O (N N) ...

En fait, nous avons supposons que le tableau donné

permet d'avoir 2 tableaux de taille N (ce serait le pire des cas) ... L'un est dédié pour les lignes d'indexation et d'autres colonnes ... Mettre ceux avec un [i] [1] = 0 dans une matrice, puis un [1] [j] = 0 dans un autre ..

Ensuite, prendre ces valeurs uniquement et vérifier la deuxième rangée et ... colums De cette manière, nous obtenons les valeurs des lignes et colonnes où il y a seulement 0, 's entièrement ...

Le nombre de valeurs dans le tableau de ligne donne nombre de 0 dans le tableau de résultat et les points a [valeurs ligne-tableau] [valeur de tableau de colonne] vous donne ces points ....

Nous pourrions le résoudre en dessous de O (N N) et le pire est O (N N) ... Comme on peut le SEEE, les tableaux (de taille N) diminue ....

Je l'ai fait quelques tableaux et a obtenu le résultat pour tous ...:)

S'il vous plaît me corriger si je me trompe partout ...

Merci pour tous vos gars commentaires ... Vous êtes très serviable et j'ai appris pas mal de choses sur le chemin ...:)

Autres conseils

Dans le pire des cas, vous devrez peut-être basculer N * N - N bits de 0 à 1 pour générer la sortie. Il semblerait que vous êtes assez bien coincé avec O (N * N).

Je suppose que vous pouvez l'optimiser pour le meilleur des cas, mais je suis tenté de dire que votre pire des cas est toujours O (N * N): Votre pire des cas sera un tableau de tous 0s, et vous doivent examiner chaque élément.

L'optimisation impliquerait sauter une ligne ou une colonne dès que vous avez trouvé un « 1 » (je peux fournir des détails, mais vous avez dit que vous ne se soucient pas de O (N * N) », mais à moins que vous avez des métadonnées à indiquent que toute une ligne / colonne est vide, ou à moins que vous avez un moyen de style SIMD pour vérifier plusieurs champs à la fois (par exemple, si chaque ligne est aligné par 4, et vous pouvez lire des données vaut 32 bits, ou si vos données sous la forme d'un masque de bits), vous aurez toujours à faire face au problème d'un tableau tout à zéro.

Il est clair que, ni la matrice de sortie, ni sa version niée doit être rare (prendre une matrice avec la moitié de la première rangée sur 1 et rien d'autre à 0 à voir), donc le temps dépend de quel format vous êtes autorisé à utiliser pour la sortie. (Je suppose que l'entrée est une liste d'éléments ou quelque chose d'équivalent, sinon vous ne pouviez pas tirer profit de la matrice étant clairsemée.)

Une solution simple pour O (M + N) espace et le temps (M est le nombre de celles de la matrice d'entrée): prendre deux tableaux de longueur N remplie de ceux, itérer à travers tous ceux de l'entrée, et pour chaque laisser tomber la coordonnée X de la première matrice et la Y à partir de la deuxième. La sortie est deux réseaux, qui définissent clairement la matrice de résultat. Son (X, Y) de coordonnées est égal à 0 si et seulement si la coordonnée X de la première matrice et la coordonnée Y de la seconde sont 0

Mise à jour: en fonction de la langue, vous pouvez utiliser quelques astuces pour retourner un tableau 2D normale en faisant référence à la même ligne plusieurs fois. Par exemple en PHP:

// compute N-length arrays $X and $Y which have 1 at the column 
// and row positions which had no 1's in the input matrix
// this is O(M+N)
$result = array();
$row_one = array_fill(0,N,1);
for ($i=0; $i<N; $i++) {
    if ($Y[$i]) {
         $result[$i] = &$row_one;
    } else {
         $result[$i] = &$X;
    }
}
return $result;

Bien sûr, cela est un tableau normal aussi longtemps que vous ne tentez pas de l'écrire.

Étant donné que chaque entrée de la matrice doit être vérifié, votre pire des cas va toujours être N * N.

Avec un petit 2 * N stockage supplémentaire, vous pouvez effectuer l'opération en O (N * N). Il suffit de créer un masque pour chaque ligne et un autre pour chaque colonne - analyse le tableau et mettre à jour les masques que vous allez. analyser ensuite à nouveau pour remplir la matrice de résultat sur la base des masques.

Si vous faites quelque chose où la matrice d'entrée est en train de changer, vous pouvez stocker un nombre d'entrées non nulles pour chaque ligne et colonne de l'entrée (plutôt qu'un masque simple,). Puis, quand une entrée dans l'entrée change, vous mettez à jour les comptes en conséquence. À ce moment-là, je laisserais tomber la matrice de sortie entièrement et interroger les masques / compte directement plutôt que même le maintien de la matrice de sortie (qui pourrait également être mis à jour le changement chose en moins de N N temps si vous voulez vraiment garder autour). Ainsi, le chargement de la matrice initiale serait encore O (N N), mais les mises à jour pourrait être beaucoup moins.

La matrice d'entrée peut être rare, mais à moins que vous pouvez l'obtenir dans un format creux (à savoir une liste de paires de (i,j) qui sont initialement), la simple lecture de votre entrée consommera O (n ^ 2) temps. Même avec l'entrée clairsemée, il est facile de se retrouver avec O (n ^ 2) sortie à écrire. En tant que triche, si vous vous laissiez à la sortie une liste de lignes fixes et des colonnes ensemble, alors vous pourriez descendre à temps linéaire. Il n'y a pas de magie à avoir lorsque votre algorithme a fait pour produire un résultat plus important que « oui » ou « non ».

Commentaire de Mcdowella sur une autre réponse suggère un autre format d'entrée alternatif: encodage RLE. Pour une entrée clairsemée, qui nécessite manifestement pas plus que O (n) temps de le lire (combien de transitions considèrent il y a entre 0 et 1). Cependant, à partir de là elle tombe en panne. Considérons une matrice d'entrée structurée comme suit:

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . . . 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . .
.     .
.       .
.         .

C'est, en alternance 0 et 1 sur la première ligne, 0 partout ailleurs. Il est clair que rares, car il y a ceux n/2 au total. Cependant, la sortie de RLE doit répéter ce modèle dans chaque ligne, ce qui conduit à O (n ^ 2) de sortie.

Vous dites:

nous devrions obtenir la sortie comme ...

Vous devez sortir la totalité de la matrice, qui a N ^ 2 éléments. Ceci est O (N * N).

Le problème est lui-même pas O (N * N): vous ne devez calculer et stocker la totalité de la matrice: vous avez seulement besoin de deux vecteurs, L et C, chacun de taille N:

L [x] est égal à 1 si x ligne est une ligne de ceux, 0 autrement;

C [x] est égal à 1 si x ligne est une ligne de ceux, 0 autrement;

On peut construire ces vecteurs à O (N), parce que la matrice initiale sont rares; vos données d'entrée ne sera pas une matrice, mais une liste contenant les coordonnées (ligne, colonne) de chaque élément non nul. En lisant cette liste, vous définissez L [en ligne] = 1 et C [colonne] = 1, et le problème est résolu: M [l, c] == 1 si L [l] == 1 ou C [c] = = 1

Il est clair pour travailler de O(N^2) à faire. Dans la matrice

tous les bits doivent être mis à 1, et N*(N-1) ne sont pas mis à un (20, en l'occurrence de 5x5).

A l'inverse, vous pouvez venir avec un algorithme qui toujours fait dans le temps de O(N^2): somme le long de la rangée supérieure et laisser la colonne, et si la ligne ou la colonne obtient une réponse non nulle, remplir toute la ligne ou la colonne; puis résoudre le problème plus petit (N-1) x (N-1).

Donc, il existe des cas qui doivent prendre au moins N^2 et tous les cas peuvent être résolus dans N^2 sans espace supplémentaire.

Si votre matrice est clairsemée, la complexité dépend beaucoup du codage d'entrée et son en particulier pas bien mesuré dans NN ² ou quelque chose comme ça, mais en termes de N votre complexité entrée M ^en et votre complexité sortie M ^sur. J'attends quelque chose comme O (N + M ^dans + M ^sur) mais beaucoup en fonction de l'encodage et les astuces que vous pouvez jouer avec.

Cela dépend entièrement de votre structure de données d'entrée. Si vous passez votre matrice (1 et 0) comme un tableau 2D que vous devez traverser et qui est O (N ^ 2). Mais comme les données sont rares, si vous passez uniquement les 1 de comme entrée, vous pouvez le faire de sorte que le ouptut est O (M), où M est pas le nombre de cellules, mais le nombre de cellules 1. Ce serait quelque chose de similaire à ce (pseudo-code ci-dessous):

list f(list l) {
   list rows_1;
   list cols_1;

    for each elem in l {
        rows_1[elem.row] = 1;
        cols_1[elem.col] = 1;
    }

    list result;
    for each row in rows_1 {
        for each col in cols_1 {
             if (row == 1 || col == 1) {
                 add(result, new_elem(row, col));
             }
        }
    } 
   return result;
}

Ne remplissez pas le centre de la matrice lorsque vous vérifiez les valeurs. En parcourant les éléments, quand on a fixé l'élément 1 correspondant à la première rangée et la première colonne. Puis revenez en arrière et remplissez vers le bas et à travers.

modifier. En fait, cela est la même chose que Andy

Cela dépend de votre structure de données.

Il n'y a que deux cas possibles pour les lignes:

une rangée i est rempli avec des 1 s'il y a un élément (i, _) dans l'entrée
Toutes les autres lignes sont identiques: à savoir le j-ième élément est une ssi il existe un élément (_, j) dans l'entrée

D'où le résultat pourrait être représenté de manière compacte comme un tableau de références à des rangées. Étant donné que nous avons seulement besoin de deux lignes le résultat consommerait également que O (N) mémoire. À titre d'exemple, cela pourrait être mis en œuvre en python comme suit:

def f(element_list, N):
  A = [1]*N
  B = [0]*N
  M = [B]*N
  for row, col in element_list:
    M[row] = A
    B[col] = 1
  return M

Un appel échantillon serait

 f([(1,1),(2,2),(4,3)],5)

avec le résultat

[[0, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 0], [1, 1, 1, 1, 1]]

Le point important est que les tableaux ne sont pas copiés ici, à savoir M [suite] = A est juste une affectation d'une référence. D'où la complexité est O (N + M), où M est la longueur de l'entrée.

#include<stdio.h>

inclure

int main () { int arr [5] [5] = {{1,0,0,0,0}, {0,1,1,0,0}, {0,0,0,0,0}, {1,0,0,1,0}, {0,0,0,0,0}}; int var1 = 0, var2 = 0, i, j;

for(i=0;i<5;i++)
   var1 = var1 | arr[0][i];

for(i=0;i<5;i++)
   var2 = var2 | arr[i][0];

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
      if(arr[i][j])
         arr[i][0] = arr[0][j] = 1;

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
          arr[i][j] = arr[i][0] | arr[0][j];

for(i=0;i<5;i++)
   arr[0][i] = var1;

for(i=0;i<5;i++)
   arr[i][0] = var2;

for(i=0;i<5;i++)
{
   printf("\n");             
   for(j=0;j<5;j++)
      printf("%d ",arr[i][j]);
}

getch();

}

Ce programme utilise seulement 2 4 variables temporaires (var1, var2, i et j) et donc fonctionne dans l'espace constant avec la complexité du temps O (n ^ 2) .. Je pense qu'il est totalement impossible à résoudre ce problème en

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow