Frage Suchen Sie die Zeile, die die kleinste Ganzzahl in einer nach Zeilen sortierten Matrix darstellt


Diese Frage wurde mir kürzlich in einem telefonischen Interview mit Java gestellt:

Sie erhalten eine NxN-Binärmatrix (0-1) mit folgenden Eigenschaften:

  • Jede Reihe ist sortiert (Folge von Nullen, gefolgt von einer Folge von Nullen)
  • Jede Zeile repräsentiert eine vorzeichenlose Ganzzahl (durch Lesen der Bits)
  • Jede Zeile ist einzigartig

Beispiel:

0 1 1
1 1 1
0 0 1

Die Bitwerte in jeder Zeile sind sortiert und die Zeilen repräsentieren die ganzen Zahlen 3, 7 und 1.

Suchen Sie die Zeile, die die kleinste Ganzzahl darstellt. Im obigen Beispiel lautet die Antwort Zeile 3, die die Ganzzahl 1 darstellt.

Ich begann mit roher Gewalt von quadratischer Komplexität. Der Interviewer antwortete, dass ich das sortierte Eigentum nicht ausnutze.

Nachdem ich viel nachgedacht hatte, benutzte ich die binäre Suche in jeder Zeile und es kam zu O (nlogn). Er fragte, ob ich mich noch verbessern könnte. Ich habe viel nachgedacht, aber ich habe mich nicht verbessert.

Ich würde mich freuen, wenn irgendjemand irgendwelche Hinweise geben könnte, um es zu verbessern.

Ein anderes Beispiel:

0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1

Die Antwort lautet Zeile 3, die die ganze Zahl 0 darstellt.


65
2017-11-29 12:45


Ursprung


Antworten:


Beginnen Sie mit Zeile 1. Gehen Sie nach rechts, bis Sie die erste treffen 1. Gehen Sie dann zu Zeile 2, aber bleiben Sie in derselben Spalte und wiederholen Sie den Vorgang, bis Sie auf a drücken 1. Mach das wiederholt. Die Reihe, in der du zuletzt richtig gegangen bist, ist deine Antwort.

Dies ist eine O (N + M) -Lösung (für eine NxM-Matrix oder O (N) für eine quadratische N × N-Matrix wie in der Frage angegeben).

Anhand Ihres Beispiels:

0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1

Das .Hier steht der durchlaufene Pfad:

. . 1 1
0 . . .
0 0 0 . . Last right step, therefore this is our answer
1 1 1 1 .

Diese Lösung arbeitet mit nicht-quadratischen Matrizen, wobei eine O (N + M) -Effizienz im schlechtesten Fall für eine N × M-Matrix beibehalten wird.

Warum funktioniert das? Die Garantie, dass die Zahlen sortiert werden, bedeutet, dass jede Reihe aus einer Reihe von Nullen besteht, gefolgt von einer Reihe von Einsen. Die Größe einer Zeile entspricht also der Entfernung, die Sie vor dem Setzen einer 1 erreichen können. Wenn also eine Zeile Sie weiterführen kann, indem Sie nur den 0en folgen, muss sie länger sein als alles, was wir zuvor verarbeitet haben.

Python-Code:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

ans, j = 0, 0
for i, row in enumerate(li):
  while j < len(row) and row[j] == 0:
    j += 1
    ans = i

print "Row", ans+1, "".join(map(str, li[ans]))

Es gibt auch eine einfachere Lösung aufgrund der Einschränkungen, immer eine quadratische N × N-Matrix und verschiedene Zeilen zusammen zu haben. Zusammen bedeuten sie, dass die Zeile mit dem niedrigsten Wert auch beides ist 0 0 ... 0 1 oder 0 0 ... 0 0. Dies liegt daran, dass N von N + 1 möglichen Zahlen in der Matrix repräsentiert sind, so dass die "fehlende" Zahl entweder 0 ist (in diesem Fall ist der kleinste dargestellte Wert 1) oder es ist etwas anderes (der kleinste Wert ist 0).

Mit diesem Wissen überprüfen wir die zweite Spalte von rechts für eine 0. Wenn wir eine finden, schauen wir nach rechts und wenn diese eine andere 0 enthält, haben wir unsere Antwort (es kann nur eine Zeile geben, die in einer endet) 0). Andernfalls suchen wir weiter in der Spalte nach 0. Wenn wir keine andere 0 finden, war die erste, die wir gefunden haben, die Zeile, nach der wir suchen (es kann nur eine Zeile geben, die endet) 01 und da gab es kein Ende 00, das ist das kleinste).

Python-Code:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

for i, row in enumerate(li):
  if row[-2] == 0:
    ans = i
    if row[-1] == 0:
      break

print "Row", ans+1, "".join(map(str, li[ans]))

Diese Lösung beantwortet die Frage mit der geringsten Schwierigkeit in O (N), aber ihre Verallgemeinerung auf nichtquadratische NxM-Matrizen oder nicht eindeutige Zahlen ergibt ihre schlechteste Effizienz O (N ^ 2). Ich persönlich bevorzuge die erste Lösung.


101
2017-11-29 12:57



die niedrigste Zahl muss 0 oder 1 sein (weil es keine Duplikate gibt und die Zeilen sortiert sind). Alles, was Sie tun müssen, ist über die letzte Spalte zu gehen, wenn ti 0 enthält, ist die niedrigste Zahl 0, sonst ist die niedrigste Zahl 1.

BEARBEITEN - Erklärung
Im N Zeilen mit der Beschränkung, die Sie dort gesättigt haben, können maximal sein N+1 einzigartige Werte.
also muss sicher mindestens 0 oder 1 in der Matrix sein ....

Edit 2 - Algorithmus 

//assuming the matrix is 0 indexed base
for i = 0...N-1
  if M[i][N-1] == 0
    return "Value is 0 in row i";
for i = 0...N-1
  if M[i][N-2] == 0
    return "Value is 1 in row i";
//because of the explanation above the flow will never reach here.

50
2017-11-29 12:54



Da die Zahlen eindeutig sind und die Zahlen sortiert sind, ist es klar, dass für jeden Wert von N die kleinste Zahl entweder die Form [0 (N-1 mal) gefolgt von 1] oder 0 (N-mal) haben kann. .

Zum Beispiel für N = 4 die kleinste Zahl   kann entweder 0001 oder 0000 sein.

Mit anderen Worten, die zweitletzte Ziffer der Nummer, die wir finden wollen, ist 0. Die letzte Ziffer kann entweder 0 oder 1 sein

Dieses Problem reduziert sich dann auf das Auffinden dieser Muster im Array, was mit einer einfachen for-Schleife erledigt werden kann

int rowNum = -1;

for(int i=0;i<N;i++)
{
    if(arr[i][N-2]==0) //Second last digit is 0. Hence the number could be min.
    {
        rowNum = i;

        if(arr[i][N-1]==1) // If number of the form 0001 was found, keep looking for 0000
        {
            continue;
        }
        else
         //If number of the form 0000 was found, exit. 
         //No other number can be lesser than 0000
        {
            break;
        }
    }
}
return rowNum;

Dieser Algorithmus hätte eine Komplexität Auf)


41
2017-11-29 17:14



Sie möchten Zeilen mit der maximalen Anzahl von Nullen finden.

  • Anfangen bei arr[0][0]
  • Wenn es ist 0, überprüfe das Element in Richtung Recht davon, arr[0][1].
  • Wenn es nicht ist 0 dann überspringen Sie diese Zeile und Beginnen Sie mit dem Überprüfen des Elementes in der nächste Reihe unter dem aktuellen Element.

Machen Sie weiter, bis Sie die letzte Zeile / letzte Spalte überschritten haben oder Sie eine Zeile mit allen Nullen finden.

Algorithmus:

i = 0 
j = 0 
answer = 0 

# continue till i is a valid index.
while(i<N) 

        # continue till j is valid index and ele is 0.
        while(j < N AND arr[i][j] == 0)

                # move towards right.
                j++ 

                #update answer.
                answer = i 

                # found a row with all zeros.
                if(j == N)  
                        break all loops.
                end-if

        end-while

        # skip current row..continue on next row.    
        i++ 

end-while

print answer

Die Komplexität davon ist O(N+N) welches ist O(N)Das ist linear.

Java-Implementierung

Verwandte Frage Das macht genau den gleichen Trick

Wie effizient in einer geordneten Matrix suchen?


24
2017-11-29 12:55



Start at the top-left.

The first row is the best row so far.

Repeat until you reach the bottom:
  If you're not already over a 1:
    Go right until you find a 1.
    This row is the best row so far.
  Go down one row.

Report the best row that was found.

Du gehst nie nach oben oder nach links - du gehst nur (n-1) mal runter und nicht mehr als (n-1) mal, was dieses O (n) macht. Dies nutzt die Sortierung, indem Sie erkennen, dass Sie nie nach links gehen müssen, um nach einer 1 zu suchen - wenn es irgendwo links eine 1 gibt, dann gibt es auch eine 1 an der aktuellen Stelle (und somit ist die Zahl in dieser Reihe mindestens so groß wie der in der vorherigen Reihe).


3
2017-11-29 13:01



Da die Bits in jeder Zeile sortiert sind, müssen alle Bits rechts 1 sein, nachdem Sie ein 1-Bit gefunden haben. Mit anderen Worten speichert das Array nur Werte der Form 2 ^ n-1.

Die Antwort lautet also, dass die Zeile mit den meisten Nulleinträgen die kleinste ist.

Da jedoch nur 2 ** m-1 Einträge vorhanden sein können, und es gibt n davon, und keine zwei sind gleich, können wir mehr ableiten - für jedes N gibt es N + 1 solche Werte. Also muss entweder 0 oder 1 vorhanden sein, da wir wissen, dass es keine Duplikate gibt.

Suchen Sie also nach einer leeren Zeile (die nur eine mit der äußersten rechten Null ist). Wenn Sie es nicht finden, ist die Antwort 1, sonst ist es 0.

AUF)


3
2017-11-29 12:53



Wie wäre es, jede Zeile in umgekehrter Reihenfolge zu durchlaufen und zu prüfen, wo die 1en enden und die Nullen beginnen?

In der Tat ist es garantiert, dass NxNDer schlechteste Fall ist, dass 0 nicht da sein wird. Sie können also nur die letzten 2 Einträge jeder Zeile überprüfen. Das macht es linear.

Da meine Erklärung nicht verstanden wurde, hier ist es in etwas Pseudo-Code:

int lowestRow = -1;
for (k = 0; k < array.length; k ++) {
   byte[] row = array[k];
   if (row[row.length - 1] == 0) {
       lowestRow = k;
       break;
   }
   if (row[row.length - 2] == 0) {
       lowestRow = k;
       //possibly look for all-zeroes, so not breaking
   }
}

2
2017-11-29 12:50