Eine Liste von Zahlen wird als monoton ansteigend (oder nicht absteigend) bezeichnet, wenn jedes Element größer oder gleich dem vorhergehenden Element ist.

Zum Beispiel 1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14steigt monoton.

Bei einer monoton ansteigenden Liste positiver Ganzzahlen mit einer willkürlichen Anzahl von leeren Stellen, die mit gekennzeichnet sind ?, füllen Sie die leeren Stellen mit positiven Ganzzahlen aus, sodass so viele eindeutige Ganzzahlen wie möglich in der Liste vorhanden sind, sie jedoch monoton ansteigen.

Möglicherweise gibt es mehrere Möglichkeiten, dies zu erreichen. Jeder ist gültig.

Die resultierende Liste ausgeben.

Zum Beispiel , wenn die Eingabe ist

?, 1, ?, 1, 2, ?, 4, 5, 5, 5, ?, ?, ?, ?, 8, 10, 11, ?, 14, 14, ?, ?

Es ist garantiert, dass die Liste ohne die leeren Stellen monoton ansteigt

1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14

und Ihre Aufgabe ist es, jedem positive Ganzzahlen zuzuweisen ?, um die Anzahl der verschiedenen Ganzzahlen in der Liste zu maximieren, während sie nicht abnehmen.

Eine Zuordnung, die nicht gültig ist, ist

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 8, 10, 11, 14, 14, 14, 14, 14

Denn während es nicht abnehmend ist, hat es nur eine einzige ganze Zahl mehr als die Eingabe, nämlich 3.

In diesem Beispiel ist es möglich, sechs eindeutige positive Ganzzahlen einzufügen und die Liste nicht zu verkleinern.
Einige mögliche Wege sind:

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 8, 10, 11, 12, 14, 14, 15, 16

1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 6, 6, 7, 8, 10, 11, 13, 14, 14, 20, 200

Beides (und viele andere) wäre eine gültige Ausgabe.

Alle leeren Stellen müssen ausgefüllt werden.

Es gibt keine Obergrenze für Ganzzahlen, die eingefügt werden können. Es ist in Ordnung, wenn sehr große Ganzzahlen in wissenschaftlicher Notation gedruckt werden.

Null ist keine positive ganze Zahl und sollte niemals eingefügt werden.

Anstelle von ?Ihnen jeden konsistenten Wert kann verwendet werden, die nicht eine positive ganze Zahl ist, wie 0, -1, null, False, oder "".

Der kürzeste Code in Bytes gewinnt.

Mehr Beispiele

[input]
[one possible output] (a "*" means it is the only possible output)

2, 4, 10
2, 4, 10 *

1, ?, 3
1, 2, 3 *

1, ?, 4
1, 2, 4

{empty list}
{empty list} *

8
8 *

?
42

?, ?, ?
271, 828, 1729

?, 1
1, 1 *

?, 2
1, 2 *

?, 3
1, 3

45, ?
45, 314159265359

1, ?, ?, ?, 1
1, 1, 1, 1, 1 *

3, ?, ?, ?, ?, 30
3, 7, 10, 23, 29, 30 

1, ?, 2, ?, 3, ?, 4
1, 1, 2, 3, 3, 3, 4

1, ?, 3, ?, 5, ?, 7
1, 2, 3, 4, 5, 6, 7 *

1, ?, 3, ?, 5, ?, ?, 7
1, 2, 3, 4, 5, 6, 7, 7

1, ?, ?, ?, ?, 2, ?, ?, ?, ?, 4, ?, 4, ?, ?, 6
1, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5, 6, 6

98, ?, ?, ?, 102, ?, 104
98, 99, 100, 101, 102, 103, 104 *

Haskell , 41 Bytes

fNimmt eine Liste und gibt eine Liste zurück, wobei 0 für ?s steht.

f=scanr1 min.tail.scanl(#)0
m#0=m+1
_#n=n

Grundsätzlich erste Scan-Liste von links, wobei die Nullen durch eins mehr als das vorherige Element (oder 0 am Anfang) ersetzt werden; Scannen Sie dann von rechts und reduzieren Sie zu große Elemente, um mit denen rechts übereinzustimmen.

Probieren Sie es online! (mit wrapper zum konvertieren ?s.)

Mathematica, 84 Bytes

Rest[{0,##}&@@#//.{a___,b_,,c___}:>{a,b,b+1,c}//.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}]&

Reine Funktion, die eine Liste als Argument verwendet, wobei die leeren Stellen mit Null(wie in {1, Null, Null, 2, Null}) gekennzeichnet oder insgesamt (wie in {1, , , 2, }) gelöscht werden , und eine geeignete Liste zurückgibt (in diesem Fall {1, 2, 2, 2, 3}).

Es stellte sich heraus, dass ich den gleichen Algorithmus wie in Ørjan Johansens Haskell-Antwort verwende : Ersetzen Sie zuerst jede Nulldurch eine Zahl mehr als die Zahl auf der linken Seite ( //.{a___,b_,,c___}:>{a,b,b+1,c}), und ersetzen Sie dann jede zu große Zahl durch die Zahl auf der rechten Seite ( //.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}). Um mögliche Nulls am Anfang der Liste zu behandeln, müssen wir zunächst a 0( {0,##}&@@#) voranstellen , den Algorithmus ausführen und dann das initial 0( Rest) löschen .

Ja, ich habe Nullstattdessen Xoder so etwas gewählt, um buchstäblich ein Byte im Code zu speichern (das, das sich sonst zwischen den Kommas von befinden würde b_,,c___).

C 160

Dies wird niemals gewinnen, aber:

#define p(x)printf("%d ",x);
i=1,l=0,m=0,n;main(c,v)char**v;{for(;i<c;i++)if(*v[i]==63)m++;else{for(n=atoi(v[i]);m>0;m--)p(l<n?++l:n)p(l=n)}for(;m>0;m--)p(++l)}

Die Liste wird von den Befehlszeilenargumenten übernommen.

05AB1E , 31 23 13 Bytes

Dank Grimy 10 Bytes gespart

ε®X:D>U].sR€ß

Probieren Sie es online!

Erläuterung

ε      ]       # apply to each number in input
 ®X:           # replace -1 with X (initially 1)
    D>U        # store current_number+1 in X
        .s     # get a list of suffixes
          R    # reverse
           ۧ  # take the minimum of each

Pip , 25 23 21 Bytes

Y{Y+a|y+1}MgW PMNyPOy

Nimmt Eingaben als mehrere durch Leerzeichen getrennte Befehlszeilenargumente an. Gibt die Ergebnisliste mit einer Nummer pro Zeile aus. Probieren Sie es online! (Ich habe die Sache mit den mehrfachen Kommandozeilenargumenten durcheinandergebracht, weil es sehr schwierig wäre, 25 Argumente für TIO hinzuzufügen, aber es funktioniert auch so, wie es angekündigt wurde.)

Erläuterung

Wir fahren in zwei Durchgängen fort. Zunächst ersetzen wir jeden Lauf von ?s in der Eingabe durch eine Sequenz, die mit der vorherigen Nummer in der Liste beginnt und jedes Mal um eins zunimmt:

? 1 ? 1 2 ? 4 5 5 5 ? ? ? ? 8 10 11 ?  14 14 ?  ?
1 1 2 1 2 3 4 5 5 5 6 7 8 9 8 10 11 12 14 14 15 16

Dann durchlaufen wir noch einmal; Für jede Zahl geben wir das Minimum und alle Zahlen rechts davon aus. Dies senkt die zu hohen Zahlen, um die Monotonie aufrechtzuerhalten.

                      y is initially "", which is 0 in numeric contexts
                      Stage 1:
 {       }Mg           Map this function to list of cmdline args g:
   +a                  Convert item to number: 0 (falsey) if ?, else nonzero (truthy)
     |                 Logical OR
      y+1              Previous number +1
  Y                    Yank that value into y (it is also returned for the map operation)
Y                      After the map operation, yank the whole result list into y
                      Stage 2:
            W          While loop, with the condition:
               MNy      min(y)
              P         printed (when y is empty, MN returns nil, which produces no output)
                  POy  Inside the loop, pop the leftmost item from y

Python 2 mit NumPy, 163 Bytes

8 Bytes dank @wythagoras gespart

Nullen kennzeichneten leere Stellen

import numpy
l=[1]+input()
z=numpy.nonzero(l)[0]
def f(a,b):
 while b-a-1:a+=1;l[a]=l[a-1]+1;l[a]=min(l[a],l[b])
i=1
while len(z)-i:f(z[i-1],z[i]);i+=1
print l[1:]

Mit Kommentaren besser lesbar:

import numpy
l=[1]+input()           # add 1 to the begining of list to handle leading zeros
z=numpy.nonzero(l)[0]   # get indices of all non-zero values
def f(a,b):             # function to fill gap, between indices a and b
    while b-a-1:
        a+=1
        l[a]=l[a-1]+1   # set each element value 1 larger than previous element
        l[a]=min(l[a],l[b])   # caps it by value at index b
i=1
while len(z)-i:       
    f(z[i-1],z[i])      # call function for every gap
    i+=1
print l[1:]             # print result, excluding first element, added at the begining

PHP, 95 77 71 69 68 Bytes

for($p=1;$n=$argv[++$i];)echo$p=$n>0?$n:++$p-in_array($p,$argv)," ";

Nimmt Eingaben von Befehlszeilenargumenten entgegen und druckt eine durch Leerzeichen getrennte Liste. Laufen Sie mit -nr.

Nervenzusammenbruch

for($p=1;$n=$argv[++$i];)   # loop through arguments
    echo$p=                     # print and copy to $p:
    $n>0                            # if positive number
        ?$n                             # then argument
        :++$p                           # else $p+1 ...
            -in_array($p,$argv)         # ... -1 if $p+1 is in input values
    ," ";                       # print space

$nist für jede Zeichenfolge als die leere Zeichenfolge und wahr "0".
$n>0ist wahr für positive Zahlen - und Zeichenketten, die sie enthalten.

Perl 6 , 97 Bytes

{my $p;~S:g/(\d+' ')?<(('?')+%%' ')>(\d*)/{flat(+($0||$p)^..(+$2||*),(+$2 xx*,($p=$2)))[^+@1]} /}

Die Eingabe ist entweder eine Liste von Werten oder eine durch Leerzeichen getrennte Zeichenfolge, ?in der die zu ersetzenden Werte angegeben werden.

Die Ausgabe ist eine durch Leerzeichen getrennte Zeichenfolge mit einem nachgestellten Leerzeichen.

Versuch es

Erweitert:

{                       # bare block lambda with implicit parameter ｢$_｣

    my $p;              # holds the previous value of ｢$2｣ in cases where
                        # a number is sandwiched between two replacements

    ~                   # stringify (may not be necessary)
    S                   # replace
    :global
    /
        ( \d+ ' ' )?    # a number followed by a space optionally ($0)

        <(              # start of replacement

          ( '?' )+      # a list of question marks
          %%            # separated by (with optional trailing)
          ' '           # a space

        )>              # end of replacement

        (\d*)           # an optional number ($2)

    /{                  # replace with the result of:

        flat(

          +( $0 || $p ) # previous value or 0
          ^..           # a range that excludes the first value
          ( +$2 || * ), # the next value, or a Whatever star

          (
            +$2 xx *,   # the next value repeated endlessly

            ( $p = $2 ) # store the next value in ｢$p｣
          )

        )[ ^ +@1 ]      # get as many values as there are replacement chars
    } /                 # add a space afterwards
}

JavaScript (ES6), 65 Byte

a=>a.map(e=>a=e||-~a).reduceRight((r,l)=>[r[0]<l?r[0]:l,...r],[])

Weil ich nutzen wollte reduceRight. Erläuterung: mapErsetzt jeden falschen Wert durch einen Wert mehr als den vorherigen, wird reduceRightvon Ende an zurückgearbeitet und sichergestellt, dass kein Wert den folgenden Wert überschreitet.

Q, 63 Bytes

{1_(|){if[y>min x;y-:1];x,y}/[(|){if[y=0;y:1+-1#x];x,y}/[0,x]]}

Im Wesentlichen derselbe Algorithmus wie bei Ørjan Johansens Haskell-Antwort .

• Geht davon aus ? = 0.
• Fügt am Anfang des Arrays eine 0 ein, falls? am Anfang.
• Durchsucht das Array und ersetzt 0 durch 1 + vorheriges Element.
• Kehrt das Array um und durchsucht es erneut, wobei Elemente, die größer als das vorherige Element sind, durch das vorherige Element ersetzt werden.
• Kehrt das erste Element um und schneidet es aus (die von Anfang an hinzugefügte 0).

Die Verwendung von min vs last wurde verwendet, um ein Byte zu speichern, da davon ausgegangen werden kann, dass das letzte Element das min-Element ist, wenn die Sortierung des Arrays absteigend ist.

TI-Basic (TI-84 Plus CE), 81 Byte

not(L1(1))+L1(1→L1(1
For(X,2,dim(L1
If not(L1(X
1+L1(X-1→L1(X
End
For(X,dim(L1)-1,1,-1
If L1(X)>L1(X+1
L1(X+1→L1(X
End
L1

Ein einfacher Port von Ørjan Johansens Haskell-Antwort auf TI-Basic. Verwendet 0 als Nullwert. Übernimmt die Eingabe von L ₁ .

Erläuterung:

not(L1(1))+L1(1→L1(1 # if it starts with 0, change it to a 1
For(X,2,dim(L1     # starting at element 2:
If not(L1(X              # if the element is zero
1+L1(X-1→L1(X            # change the element to one plus the previous element
End
For(X,dim(L1)-1,1,-1 # starting at the second-last element and working backwards
If L1(X)>L1(X+1           # if the element is greater than the next
L1(X+1→L1(X               # set it equal to the next
End
L1                   # implicitly return

Java 8, 199 164 Bytes

a->{for(int l=a.length,n,j,x,i=0;i<l;)if(a[i++]<1){for(n=j=i;j<l;j++)if(a[j]>0){n=j;j=l;}for(j=i-3;++j<n-1;)if(j<l)a[j+1]=j<0?1:a[j]+(l==n||a[n]>a[j]|a[n]<1?1:0);}}

Ändert das Eingabe-Array, anstatt ein neues zurückzugeben, um Bytes zu sparen.
Verwendet 0anstelle von ?.

Probieren Sie es online aus.

Erläuterung:

a->{                      // Method with integer-array parameter and no return-type
  for(int l=a.length,     //  Length of the input-array
      n,j,x,              //  Temp integers
      i=0;i<l;)           //  Loop `i` over the input-array, in the range [0, length):
    if(a[i++]<1){         //   If the `i`'th number of the array is 0:
                          //   (And increase `i` to the next cell with `i++`)
      for(n=j=i;          //    Set both `n` and `j` to (the new) `i`
          j<l;j++)        //    Loop `j` in the range [`i`, length):
        if(a[j]>0){       //     If the `j`'th number of the array is not 0:
          n=j;            //      Set `n` to `j`
          j=l;}           //      And set `j` to the length to stop the loop
                          //    (`n` is now set to the index of the first non-0 number 
                          //     after the `i-1`'th number 0)
      for(j=i-3;++j<n-1;) //    Loop `j` in the range (`i`-3, `n-1`):
        if(j<l)           //     If `j` is still within bounds (smaller than the length)
          a[j+1]=         //      Set the `j+1`'th position to:
            j<0?          //       If `j` is a 'position' before the first number
             1            //        Set the first cell of the array to 1
            :             //       Else:
             a[j]+        //        Set it to the `j`'th number, plus:
              (l==n       //        If `n` is out of bounds bounds (length or larger)
               ||a[n]>a[j]//        Or the `n`'th number is larger than the `j`'th number
               |a[n]<1?   //        Or the `n`'th number is a 0
                1         //         Add 1
               :          //        Else:
                0);}}     //         Leave it unchanged by adding 0

Python 2 , 144 124 119 Bytes

l=input()
for n in range(len(l)):a=max(l[:n]+[0]);b=filter(abs,l[n:]);b=len(b)and b[0]or-~a;l[n]=l[n]or a+(b>a)
print l

Probieren Sie es online!

Verwendet 0anstelle von?

JavaScript (ES6), 59

Eine Funktion mit einem Integer-Array als Eingabe. Die leeren Stellen sind mit gekennzeichnet0

a=>a.map((v,i)=>v?w=v:(a.slice(i).find(x=>x)<=w?w:++w),w=0)

Prüfung

var F=
a=>a.map((v,i)=>v?w=v:(a.slice(i).find(x=>x)<=w?w:++w),w=0)

;[[2, 4, 10]
,[1, 0, 3]
,[1, 0, 4]
,[]
,[8]
,[0]
,[0, 0, 0]
,[0, 1]
,[0, 2]
,[0, 3]
,[45, 0]
,[1, 0, 0, 0, 1]
,[3, 0, 0, 0, 0, 30]
,[1, 0, 2, 0, 3, 0, 4]
,[1, 0, 3, 0, 5, 0, 7]
,[1, 0, 3, 0, 5, 0, 0, 7]
,[1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 4, 0, 4, 0, 0, 6]
,[98, 0, 0, 0, 102, 0, 104]]
.forEach(a=>{
  console.log(a+'\n'+F(a))
})

C # (.NET Core) , 182 Byte

Mit der gleichen Strategie wie Ørjan Johansen.

Verwendet 0 in der Eingabeliste, um die unbekannte Variable zu markieren.

l=>{if(l[0]<1)l[0]=1;int j;for(j=0;j<l.Length;j++)l[j]=l[j]==0?l[j-1]+1:l[j];for(j=l.Length-2;j>=0;j--)l[j]=l[j]>l[j+1]?l[j+1]:l[j];foreach(var m in l) System.Console.Write(m+" ");};

Probieren Sie es online!

Perl 5 -p , 99 Bytes

s,(\d+ )?\K((\? )+)(?=(\d+)),$d=$1;$l=$4;$2=~s/\?/$d<$l?++$d:$l/rge,ge;($d)=/.*( \d+)/;s/\?/++$d/ge

Probieren Sie es online!