Введение

По определению, уникальные идентификаторы должны быть уникальными. Наличие нескольких одинаковых идентификаторов приводит к получению неожиданных данных. Но поскольку данные поступают одновременно из нескольких источников, может быть сложно обеспечить уникальность. Напишите функцию, которая унифицирует список идентификаторов.

Возможно, это худший пазл из всех, что я написал, но вы поняли.

Требования

Учитывая список от нуля или более натуральных чисел, примените следующие правила к каждому числу от первого до последнего:

• Если номер первый в своем роде, сохраните его.
• Если число встречалось ранее, замените его наименьшим положительным целым числом, которого нет нигде во всем списке ввода или в любом существующем выводе.

Для решения:

• Решением может быть программа или функция.
• Ввод может быть строкой, массивом, переданным в качестве аргументов, или вводом с клавиатуры.
• Вывод может быть строкой, массивом или выводиться на экран.
• Все числа в списке вывода различны.

Предположения

• Список ввода чистый. Он содержит только положительные целые числа.
• Целое положительное число имеет диапазон от 1 до 2 ³¹ -1.
• Менее 256 МБ памяти доступно для переменных вашей программы. (Как правило, массивы из 2 147 483 648 элементов не допускаются.)

Тестовые случаи

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

счет

Просто простой код гольф. Наименьшее количество байтов к этому времени на следующей неделе побеждает.

Брахилог , 8 байт

{|∧ℕ₁}ᵐ≠

Попробуйте онлайн!

объяснение

{    }ᵐ     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 байта

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++)чтобы .contains(++m+c);)сохранить 1 байт, и одновременно преобразовать в Java 8, чтобы сохранить еще 13 байт.

Пояснения:

Попробуй это здесь.

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 байт

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

Рубин , 63 байта

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

Попробуйте онлайн!

объяснение

->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 байт

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

Попробуйте онлайн!

объяснение

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 байт

<?$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);

Онлайн версия

расширенный

$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 байт

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

Берет ввод с клавиатуры, вроде [3, 3, 3, 3, 3, 3].

Просто следите за наименьшим положительным целым числом, которое jдо сих пор не использовалось. Для каждого элемента xввода выведите, xесли он xеще не использовался, в противном случае выведите j. Наконец, обновляйте jкаждый раз, когда вы что-то выводите.

РЕДАКТИРОВАНИЕ: исправить ошибку при обработке ввода [6, 6, 4, 4, 2, 2]. Спасибо @Rod за указание на ошибку, а также на исправление. Ошибка заключалась в том, что в случае дублирования записи он вывел бы наименьшее число, не использованное для этой точки в списке, даже если этот вывод появился позже во входных данных. (Это было неправильно, как поясняется в посте и комментариях, но я все равно как-то испортил это.) В любом случае, исправление состояло в том, чтобы просто добавить список ввода aк набору значений, которые в этом случае не могли быть выведены.

Haskell , 79 76 байт

РЕДАКТИРОВАТЬ:

• -3 байта: @nimi видел, что headможет быть заменено сопоставлением с образцом.

([]#)анонимная функция, принимающая и возвращающая список Используйте как ([]#)[2147483647, 2, 2147483647, 2].

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

Попробуйте онлайн!

Как это работает

• ? является сокращенным оператором для проверки отсутствия элемента в списке.
• s#lобрабатывает список целых чисел l, учитывая список sуже используемых целых чисел.
  • xэто следующее целое число, чтобы посмотреть, yостальные.
  • zцелое число, выбранное для следующего места. Это xесли xне является элементом s, и первое положительное целое число ни в, sни в yдругом.
  • (z:s)#yзатем возвращается с zдобавленным в список целых чисел.
  • n является пустым списком, поскольку непустые списки были обработаны в предыдущей строке.
• Основная функция ([]#)принимает список и вызывает #его как второй аргумент, а также пустой список для первого аргумента.

APL (Dyalog 16.0), 34 байта

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

Pyth , 21 20 байт

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

Тестирование

Я добавлю объяснение, когда у меня будет время.

C # , 135 байт

Golfed

(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 читаемый

// 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;
};

Полный код

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();
      }
   }
}

релизы

• v1.0 - 135 bytes- Исходное решение.

Заметки

• Никто

Python 2 , 101 байт

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

Попробуйте онлайн! или попробуйте все тестовые случаи

R , 39 46 байт

Создает вектор из входных данных, затем заменяет дублированные значения диапазоном от 1 до миллиона, в которых удалены входные значения. Возвращает числовой вектор. Нет ввода вернет пустой вектор числовой (0).

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

Попробуйте онлайн!

Это выдаст предупреждение о длине вектора замены

                           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 байтов 133 байта

вход = массив а, выход = модифицированный массив а

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;}}

отформатированные

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;
            }
}

Слишком много байтов потрачено на эти циклы. Кто-нибудь думает о сокращении кода, изобретая новый алгоритм (который использует меньше цикла)? Я думал, но не нашел один.

C # 7, 116 байт

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();}

изрезанный

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();
}

Разъяснения

• первое вхождение числа всегда остается как есть
• последовательные вхождения числа взяты из [1, 2, 3, ...], пропуская значения, присутствующие во входных данных.

Онлайн версия

Clojure, 72 байта

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

Основное сокращение. Если iдо сих пор содержится в выходном списке, мы возьмем 2-й элемент (1 при 0-индексированном) из бесконечного списка целых чисел, (range)из которого мы удалили те числа, которые уже были использованы. Диапазон начинается с нуля, поэтому мы не можем взять первый элемент, но второй.

R, 74 байта

читает список со стандартного ввода; возвращает NULL для пустого ввода.

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

объяснение:

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) могут быть использованы, поскольку мы гарантированно никогда не нуждаемся в замене за пределами этого диапазона.

Попробуйте онлайн!

Аксиома, 169 байт

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)

разгул и результат

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