Neuen Eintrag in Tabelle einfügen

[hallowelt543]

Ein Young-Tableau ist eine m×n-Matrix (ti,j) mit Einträgen für die gilt, dass in jeder Zeile und jeder Spalte die Werte von links nach rechts bzw. von oben nach unten aufsteigen. Die Einträge mit Wert ∞ stehen dabei für leere Stellen.
Geben Sie einen Algorithmus an, der in Laufzeit O(n + m) einen neuen Eintrag in ein (nicht-volles) Young-Tableau einfügt, und beschreiben Sie seine Funktionsweise
#Meine Überlegung:

x:= neuer Eintrag
for i to n do
      for j to m do
          if ti,j  ungleich unendlich then
               if x > ti-1,j und x> ti, j-1 then
                    ti,j = x
               endif
          endif
      endfor
endfor

Jedoch komm ich auf eine Komplexität von O(n*m)... hat jemand vielleicht eine wie ich den Code umschreiben könnte um O(n+m) zu erreichen.
(Also mein Algorithmus würde jeden Eintrag der Zeile überprüfen und dann schauen ob der linke und der obere größer sind und würde dann den neuen Eintrag einsetzen.)

 

[httpdigest]

Also mit der Bedingung, dass rechte Zellen in derselben Zeile bzw. untere Zellen in derselben Spalte immer in ihrem Wert aufsteigen müssen, und leere Zellen den Wert unendlich haben, folgt ja zwangsweise daraus, dass rechts neben bzw. unter einer leeren/unendlichen Zelle keine nicht-unendliche Zelle mehr kommen kann. Also brauchst du streng genommen nur die letzte Spalte (einfach von unten nach oben) oder die letzte Zeile (einfach von rechts nach links) nach einem unendlichen/leeren Wert prüfen und dann noch soweit nach oben/links gehen, bis du einen nicht-unendlichen Wert findest, und dann einfach dessen rechten/unteren Nachbarn auf max(links, oben)+1 setzen.

 

[hallowelt543]

danke erstmal für die Antwort aber irgendwie versteh ich nicht ganz wie du es meinst.. könntest du es vielleicht grob in einen Pseudocode schreiben, damit ich deine Vorgehensweise verstehe ?

 

[mihe7]

Was gibt es daran nicht zu verstehen? Du fängst unten rechts an, gehst erst nach oben, dann nach links - jeweils so lange, bis kein leeres Feld mehr verfügbar ist. Fertig.