Einführung

Per Definition sollten eindeutige Bezeichner eindeutig sein. Wenn mehrere Identifikatoren identisch sind, ruft einer unerwartete Daten ab. Bei Daten, die gleichzeitig aus mehreren Quellen eingehen, kann es jedoch schwierig sein, die Eindeutigkeit sicherzustellen. Schreiben Sie eine Funktion, die eine Liste von Bezeichnern eindeutig macht.

Dies ist möglicherweise der schlimmste Puzzle-Flaum, den ich geschrieben habe, aber Sie haben die Idee.

Bedarf

Wenden Sie bei einer Liste mit null oder mehr positiven ganzen Zahlen die folgenden Regeln auf jede Zahl vom ersten bis zum letzten an:

• Wenn die Nummer die erste ihrer Art ist, bewahren Sie sie auf.
• Wenn die Zahl bereits einmal angetroffen wurde, ersetzen Sie sie durch die niedrigste positive Ganzzahl, die in der gesamten Eingabeliste oder einer vorhandenen Ausgabe nicht vorhanden ist.

Für die Lösung:

• Die Lösung kann ein Programm oder eine Funktion sein.
• Die Eingabe kann eine Zeichenfolge, ein als Argument übergebenes Array oder eine Tastatureingabe sein.
• Die Ausgabe kann eine Zeichenfolge, ein Array oder ein Ausdruck auf dem Bildschirm sein.
• Alle Zahlen in der Ausgabeliste sind unterschiedlich.

Annahmen

• Die Eingabeliste ist sauber. Es enthält nur positive ganze Zahlen.
• Eine positive ganze Zahl hat den Bereich von 1 bis 2 ³¹ -1.
• Für die Variablen Ihres Programms sind weniger als 256 MB Speicher verfügbar. (Grundsätzlich sind keine Arrays mit 2.147.483.648 Elementen zulässig.)

Testfälle

Input:  empty
Output: empty

Input:  5
Output: 5

Input:  1, 4, 2, 5, 3, 6
Output: 1, 4, 2, 5, 3, 6

Input:  3, 3, 3, 3, 3, 3
Output: 3, 1, 2, 4, 5, 6

Input:  6, 6, 4, 4, 2, 2
Output: 6, 1, 4, 3, 2, 5

Input:  2147483647, 2, 2147483647, 2
Output: 2147483647, 2, 1, 3

Wertung

Nur ein einfacher Code Golf. Die niedrigste Byteanzahl von dieser Zeit nächste Woche gewinnt.

Brachylog , 8 Bytes

{|∧ℕ₁}ᵐ≠

Probieren Sie es online!

Erläuterung

{    }ᵐ     Map on the Input:
              Input = Output…
 |            …or…
  ∧ℕ₁         …Output is in [1,+inf)
       ≠    All elements of the output must be different
            (Implicit labeling)

Java 8, 158 144 Bytes

a->{int m=0;String r="",c=",",b=r;for(int x:a)b+=x+c;for(int x:a)if(r.contains(x+c)){for(;(r+b).contains(++m+c););r+=m+c;}else r+=x+c;return r;}

• .contains(m+c);m++)um .contains(++m+c);)1 Byte zu speichern , und gleichzeitig auf Java 8 umgewandelt 13 weitere Bytes zu speichern.

Erklärungen:

Probieren Sie es hier aus.

a->{                      // Method with integer-array parameter and String return-type
  int m=0;                //  Lowest integer
  String r="",            //  Result-String
         c=",",           //  Comma delimiter for result String
         b=r;for(int x:a)b+=x+c;
                          //  Input array as String
  for(int x:a)            //  Loop (2) over the integers in the array
    if(r.contains(x+c)){  //   If the result already contains this integer
      for(;(r+b).contains(++m+c););
                          //    Inner (3) as long as either the result-String or array-String contains the lowest integer
                          //     and raise the lowest integer before every iteration by 1
      r+=m+c;             //    Append the result with this lowest not-present integer
    }else                 //   Else:
      r+=x+c;             //    Append the result-String with the current integer
                          //  End of loop (2) (implicit / single-line body)
  return r;               //  Return the result-String
}                         // End of method

JavaScript (ES6), 49 Byte

a=>a.map(g=(e,i)=>a.indexOf(e)-i?g(++n,-1):e,n=0)

Ruby , 63 Bytes

->a{r=*0..a.size;r.map{|i|[a[i]]-a[0,i]==[]?a[i]=(r-a)[1]:0};a}

Probieren Sie es online!

Erläuterung

->a{                                    # Anonymous function with one argument
    r=*0..a.size;                       # Numbers from 0 to array size
    r.map{|i|                           # For all numbers in range:
        [a[i]]                          #  Get array with just a[i]
              -a[0,i]                   #  Remove elements from array that are
                                        #    also in a[0..i-1]
                    ==[]?               #  Check if result is an empty array
                        a[i]=           #  If true, set a[i] to:
                             (r-a)      #   Remove elements from number range
                                        #     that are also in input array
                                  [1]   #   Get second element (first non-zero)
                        :0};            #  If false, no-op
                            a}          # Return modified array

05AB1E , 17 16 18 Bytes

vy¯yåi¹gL¯K¹K¬}ˆ}¯

Probieren Sie es online!

Erläuterung

v                    # for each y in input
 y                   # push y
  ¯yåi               # if y exist in global list
      ¹gL            # push [1 ... len(input)]
         ¯K          # remove any number that is already in global list
           ¹K        # remove any number that is in the input
             ¬       # get the first (smallest)
              }      # end if
               ˆ     # add to global list
                }¯   # end loop, push and output global list

PHP, 121 Bytes

<?$n=array_diff(range(0,count($g=$_GET)),$g);sort($n);$r=[];foreach($g as$v)$r[]=in_array($v,$r)?$n[++$i]:$v;print_r($r);

Online Version

Erweitert

$n=array_diff(range(0,count($g=$_GET)),$g); # create array of ascending values which are not in input array plus zero
sort($n); # minimize keys
$r=[];  # empty result array
foreach($g as$v) # loop input array
  $r[]=in_array($v,$r)?$n[++$i]:$v; # if value is not in result array add value else take new unique value skip zero through ++$i
print_r($r); # output result array

Python 2, 77 79 Bytes

a=input();u=[];j=1
for x in a:
 u+=[[x,j][x in u]]
 while j in u+a:j+=1
print u

Nimmt Tastatureingaben wie [3, 3, 3, 3, 3, 3].

Verfolgen Sie einfach die kleinste positive Ganzzahl j, die bisher nicht verwendet wurde. Für jedes Element xder Eingabe wird ausgegeben, xwenn es xnoch nicht verwendet wurde, andernfalls wird ausgegeben j. Aktualisieren jSie schließlich jedes Mal , wenn Sie etwas ausgeben.

BEARBEITET: um eine Fehlerbehandlungseingabe von zu beheben [6, 6, 4, 4, 2, 2]. Vielen Dank an @Rod für den Hinweis auf den Fehler sowie eine Fehlerbehebung. Der Fehler bestand darin, dass im Falle eines doppelten Eintrags die kleinste Zahl ausgegeben wurde, die bis zu diesem Punkt in der Liste nicht verwendet wurde, selbst wenn diese Ausgabe später in der Eingabe erschien. (Dies war falsch, wie im Beitrag und in den Kommentaren klargestellt, aber ich habe es trotzdem irgendwie durcheinander gebracht.) Trotzdem bestand die Korrektur darin, die Eingabeliste einfach azu den Werten hinzuzufügen, die in diesem Fall nicht ausgegeben werden konnten.

Haskell , 79-76 Bytes

BEARBEITEN:

• -3 Bytes: @nimi sah, dass headdurch eine Musterübereinstimmung ersetzt werden konnte.

([]#)ist eine anonyme Funktion, die eine Liste aufnimmt und zurückgibt. Verwenden Sie wie ([]#)[2147483647, 2, 2147483647, 2].

(?)=notElem
s#(x:y)|z:_<-[x|x?s]++filter(?(s++y))[1..]=z:(z:s)#y
_#n=n
([]#)

Probieren Sie es online!

Wie es funktioniert

• ? ist ein abgekürzter Operator zum Überprüfen, ob ein Element in einer Liste fehlt.
• s#lBehandelt die Liste der Ganzzahlen l, wenn eine Liste sder bereits verwendeten Ganzzahlen vorliegt.
  • xist die nächste zu betrachtende Ganzzahl, ydie übrigen.
  • zist die für den nächsten Punkt gewählte Ganzzahl. Es ist, xwenn xist kein Element von sund die erste positive ganze Zahl weder in snoch in ysonst.
  • (z:s)#ydann rekursiv mit zzur Liste der verwendeten Ganzzahlen hinzugefügt.
  • n ist eine leere Liste, da nicht leere Listen in der vorherigen Zeile behandelt wurden.
• Die Hauptfunktion ([]#)nimmt eine Liste und ruft #sie als zweites Argument und eine leere Liste für das erste Argument auf.

APL (Dyalog 16.0), 34 Bytes

(s↑v~⍨⍳⌈/v+s←+/b←(⍳≢v)≠⍳⍨v)@{b}v←⎕

Pyth , 21 bis 20 Bytes

.b?} NPY@-UhlQQ=hZNQ._
m?}edPd@-SlQQ~hZed._

Testsuite

Ich werde eine Erklärung hinzufügen, wenn ich Zeit habe.

C # , 135 Bytes

Golf gespielt

(int[] i)=>{for(int x=1,v,m=0,l=i.Length,y;x<l;x++){v=i[x];for(y=0;y<l&&v==i[x]?y<x:y<l;y++)if(i[y]==v){v=++m;y=-1;}i[x]=v;}return i;};

Ungolfed

( int[] i ) => {
   for( int x = 1, v, m = 0, l = i.Length, y; x < l; x++ ) {
      v = i[ x ];

      for( y = 0; y < l && v == i[ x ] ? y < x : y < l ; y++ )
         if( i[ y ] == v ) {
            v = ++m;
            y = -1;
         }

      i[ x ] = v;
   }

   return i;
};

Ungolfed lesbar

// Takes an array of Int32 objects ( 32-byte signed integers )
( int[] i ) => {

   // Cycles through each element on the array
   //   x: Scan position, starts at the 2nd element
   //   v: Value being processed
   //   m: The next minimum value to replace
   //   l: Size of the array, to save some byte count
   for( int x = 1, v, m = 0, l = i.Length, y; x < l; x++ ) {

      // Hold the value
      v = i[ x ];

      // Re-scan the array for a duplicate value up the the current position ( 'x' ) IF
      //   ... the currently hold value hasn't been modified
      //   ... otherwise, re-scans the entire array to find a suitable value to replace
      for( y = 0; y < l && v == i[ x ] ? y < x : y < l ; y++ )

         // Check if 'v' shares the same value with other element
         if( i[ y ] == v ) {

            // Set 'v' to the minimum value possible
            v = ++m;

            // Reset the scan position to validate the new value
            y = -1;
         }

      // Set the 'v' to the array
      i[ x ] = v;
   }

   // Return the array
   return i;
};

Vollständiger Code

using System;
using System.Collections.Generic;

namespace Namespace {
   class Program {
      static void Main( String[] args ) {
         Func<Int32[], Int32[]> f = ( int[] i ) => {
            for( int x = 1, v, m = 0, l = i.Length, y; x < l; x++ ) {
               v = i[ x ];

               for( y = 0; y < l && v == i[ x ] ? y < x : y < l ; y++ )
                  if( i[ y ] == v ) {
                     v = ++m;
                     y = -1;
                  }

               i[ x ] = v;
            }

            return i;
         };

         List<Int32[]>
            testCases = new List<Int32[]>() {
               new Int32[] { },
               new Int32[] { 5 },
               new Int32[] { 1, 4, 2, 5, 3, 6 },
               new Int32[] { 3, 3, 3, 3, 3, 3 },
               new Int32[] { 6, 6, 4, 4, 2, 2 },
               new Int32[] { 2147483647, 2, 2147483647, 2 },
            };

         foreach( Int32[] testCase in testCases ) {
            Console.WriteLine( $" Input: {String.Join( ",", testCase )}\nOutput: {string.Join( ",", f( testCase ) )}\n" );
         }

         Console.ReadLine();
      }
   }
}

Releases

• v1.0 - 135 bytes- Anfangslösung.

Anmerkungen

• Keiner

Python 2 , 101 Bytes

x=input()
for i,n in enumerate(x):x[i]=[n,list(set(range(1,len(x)+9))-set(x))[0]][n in x[:i]]
print x

Probieren Sie es online! oder Probieren Sie alle Testfälle aus

R 39 46 Bytes

Erstellt einen Vektor aus der Eingabe und ersetzt dann die duplizierten Werte durch einen Bereich von 1 bis 1 Million, bei dem die Eingabewerte entfernt wurden. Gibt einen numerischen Vektor zurück. Keine Eingabe gibt den leeren numerischen Vektor (0) zurück.

i[duplicated(i)]=(1:1e6)[-(i=scan())];i

Probieren Sie es online!

Dies gibt eine Warnung über die Länge des Ersatzvektors aus

                           i=scan()     # set i as input
                 (1:1e6)                # 1 to a million (could go higher)
                 (1:1e6)[-(i=scan())]   # without input values
  duplicated(i)                         # duplicate values in i
i[duplicated(i)]=(1:1e6)[-(i=scan())]   # set duplicate i values to reduced range vector
                                     ;i # return result

C 169 Bytes 133 Bytes

Eingabe = Array a, Ausgabe = modifiziertes Array a

i=1,j,k,l;void f(int*a,int n){for(;i<n;i++)for(j=i-1;j>=0;j--)if(a[i]==a[j]){l=1;for(k=0;k<n;)if(l==a[k])k=l++?0:0;else k++;a[i]=l;}}

formatiert

int i, j, k, l;
void f(int* a, int n)
{
    for (i = 1; i<n; i++)
        for (j = i - 1; j >= 0; j--)
            if (a[i] == a[j])
            {
                l = 1;
                for (k = 0; k<n;)
                    if (l == a[k])
                        k = l++ ? 0 : 0;
                    else
                        k++;
                a[i] = l;
            }
}

Für diese Schleife wurden zu viele Bytes verschwendet. Denkt jemand daran, den Code durch die Erfindung eines neuen Algorithmus (der weniger Schleife verwendet) zu verkürzen? Ich habe nachgedacht, aber noch keinen gefunden.

C # 7, 116 Bytes

int[]f(int[]c){int j=0;int h()=>c.Contains(++j)?h():j;return c.Select((e,i)=>Array.IndexOf(c,e)<i?h():e).ToArray();}

Eingerückt

int[] f(int[] c)
{
    int j = 0;
    int h() => c.Contains(++j) ? h() : j;
    return c
        .Select((e, i) => Array.IndexOf(c, e) < i ? h() : e)
        .ToArray();
}

Erklärt

• Das erste Vorkommen einer Zahl bleibt immer unverändert
• aufeinanderfolgende Vorkommen einer Zahl werden gezogen [1, 2, 3, ...], wobei die in der Eingabe vorhandenen Werte übersprungen werden.

Online Version

Clojure, 72 Bytes

#(reduce(fn[r i](conj r(if((set r)i)(nth(remove(set r)(range))1)i)))[]%)

Eine Grundreduktion. Wenn iin der Ausgabeliste bisher enthalten ist, werden wir das 2. Element (1, wenn 0-indiziert) aus der unendlichen Liste von Ganzzahlen nehmen, (range)aus denen wir die bereits verwendeten Zahlen entfernt haben. Der Bereich beginnt bei Null, sodass wir nicht das erste Element, sondern das zweite nehmen können.

R 74 Bytes

liest die Liste von stdin; Gibt NULL für eine leere Eingabe zurück.

o=c();for(i in n<-scan())o=c(o,`if`(i%in%o,setdiff(1:length(n),o)[1],i));o

Erläuterung:

o=c()                                #initialize empty list of outputs
for(i in n<-scan())                  # loop through the list after reading it from stdin
    o=c(o,                           # set the output to be the concatenation of o and
      `if`(i%in%o,                   # if we've seen the element before
           setdiff(1:length(n),o)[1] # the first element not in 1,2,...
           ,i))                      # otherwise the element
o                                    # print the output

1:length(n) kann verwendet werden, da wir garantiert keinen Ersatz von außerhalb dieses Bereichs benötigen.

Probieren Sie es online!

Axiom, 169 Bytes

f a==(r:List INT:=[];for i in 1..#a repeat(~member?(a.i,r)=>(r:=concat(r,a.i));for j in 1..repeat if~member?(j,r)and(~member?(j,a)or j=a.i)then(r:=concat(r,j);break));r)

ungolf und ergebnis

ff(a)==
  r:List INT:=[]
  for i in 1..#a repeat
      ~member?(a.i,r)=>(r:=concat(r,a.i))
      for j in 1.. repeat
            if~member?(j,r)and(~member?(j,a) or j=a.i)then(r:=concat(r,j);break)
  r

(3) -> f([])
   (3)  []
                                                       Type: List Integer
(4) -> f([5])
   (4)  [5]
                                                       Type: List Integer
(5) -> f([1,4,2,5,3,6])
   (5)  [1,4,2,5,3,6]
                                                       Type: List Integer
(6) -> f([3,3,3,3,3,3])
   (6)  [3,1,2,4,5,6]
                                                       Type: List Integer
(7) -> f([6, 6, 4, 4, 2, 2])
   (7)  [6,1,4,3,2,5]
                                                       Type: List Integer
(8) -> f([2147483647, 2, 2147483647, 2])
   (8)  [2147483647,2,1,3]
                                                       Type: List Integer