Sea una lista de enteros positivos sin un orden particular, y que puede contener duplicados. Escriba un programa o función que genere una lista de enteros positivos M (cuyo orden no es importante) de modo que la fusión de L y M dé como resultado la lista más pequeña que puede dividirse por completo en rangos idénticos de enteros [ 1 .. i ] , donde i es el elemento más grande en $L$$M$$L$$M$$[1..i]$$i$$L$

Ejemplo

Dejar L = [5,3,3,2,7]. El elemento máximo de Les 7. La mayoría de las veces que ocurre un número entero específico es 2( 3aparece 2 veces). Por lo tanto, necesitamos generar la lista Mque permitirá completar Lpara poder construir 2rangos de enteros desde 1hasta 7.

Por lo tanto, necesitamos salida M = [1,1,2,4,4,5,6,6,7], para que cada número entero de 1a 7aparezca 2veces.

Entradas y salidas

• Use cualquier cosa en su idioma que sea similar a las listas. La estructura de datos utilizada para la entrada y la salida debe ser la misma.
• La lista de entrada contendrá solo enteros positivos.
• La lista de entrada no estará vacía.
• No puede asumir que la lista de entrada está ordenada.
• El orden en la lista de salida no es importante.

Casos de prueba

Input                  Output
[1]                    []
[7]                    [1, 2, 3, 4, 5, 6]
[1, 1, 1]              []
[1, 8]                 [2, 3, 4, 5, 6, 7]
[3, 3, 3, 3]           [1, 1, 1, 1, 2, 2, 2, 2]
[5, 2, 4, 5, 2]        [1, 1, 3, 3, 4]
[5, 2, 4, 5, 5]        [1, 1, 1, 2, 2, 3, 3, 3, 4, 4]
[5, 3, 3, 2, 7]        [1, 1, 2, 4, 4, 5, 6, 6, 7]

Puntuación

Este es el código de golf , por lo que gana la respuesta más corta en bytes.

Jalea , 9 bytes

Guardado 1 byte gracias a Jonathan Allan . El pie de página llama al enlace principal, ordena el resultado para que coincida con los casos de prueba y formatea la salida como una cuadrícula.

RṀẋLƙ`Ṁœ-

Pruébalo en línea! o echa un vistazo a una suite de prueba!

Alternativas

ṀRẋLƙ`Ṁœ-
RṀẋṢŒɠṀƊœ-
ṀRẋṢŒɠṀƊœ-
LƙɓṀRẋṀœ-⁸
LƙɓRṀẋṀœ-⁸

¡Prueba uno de ellos en línea!

Explicación

ṀRẋLƙ`Ṁœ- Programa completo. N = Entrada.
ṀR Rango de 1 a max (N): [1 ... max (N)]
   Lƙ` Longitud del mapa sobre grupos formados por elementos idénticos.
  ẋ Repita el rango T veces, para cada T en el resultado de lo anterior.
      Ṁ Máximo. Básicamente, obtenga el rango de repetición max (^^) veces.
       œ- Diferencia de conjunto múltiple con N.

Perl 6 , 37 33 bytes

-4 bytes gracias a nwellnhof!

{^.keys.max+1 xx.values.max∖$_}

Pruébalo en línea!

Bloque de código anónimo que toma una bolsa y devuelve una bolsa de valores.

Explicación:

{                             } # Anonymous code block
 ^.keys.max+1  # Create a range from 1 to the maximum value of the list
              xx  # Multiply the list by:
                .values.max      # The amount of the most common element
                           ∖$_   # Subtract the original Bag

R , 59 49 48 bytes

rep(s<-1:max(L<-scan()),max(y<-table(c(L,s)))-y)

Pruébalo en línea!

Python 2 , 86 83 80 72 bytes

def f(l):m=range(1,max(l)+1)*max(map(l.count,l));map(m.remove,l);print m

Pruébalo en línea!

05AB1E , 17 16 17 bytes

¢Z¹ZLŠŠи{ðý¹vyõ.;

-1 byte gracias a @ Mr.Xcoder .
+1 byte después de la corrección de errores de la solución temporal ...

Tal vez miro completamente más allá, pero 05AB1E incluso tiene una eliminación de todos los elementos de la lista b de la lista a ... (EDITAR: De hecho no ...) Sé cómo eliminar todas las veces múltiples, pero no una vez cada una ... (diferencia de varios conjuntos)

Definitivamente se puede jugar al golf. No estoy muy contento con eso, tbh ... Veré si puedo jugar un poco más antes de agregar una explicación. EDITAR: Se agregó una explicación.

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

¢         # Get the occurrences for each item in the (implicit) input-List
          #  i.e. [5,3,3,2,7] → [1,2,2,1,1]
 Z        # And get the maximum
          #  i.e. [1,2,2,1,1] → 2
¹Z        # Also get the maximum from the input-list itself
          #  i.e. [5,3,3,2,7] → 7
  L       # And create a list in the range [1, max]
          #  i.e. 7 → [1,2,3,4,5,6,7]
ŠŠ        # Two triple-swaps so the stack order becomes:
          # trash we don't need; ranged list; occurrence max
  и       # Repeat the ranged list the occurence amount of times
          #  i.e. [1,2,3,4,5,6,7] and 2 → [1,2,3,4,5,6,7,1,2,3,4,5,6,7]

          #Now the work-around bit because 05AB1E lacks a builtin for multiset difference..
{         # Sort the list
          #  i.e. [1,2,3,4,5,6,7,1,2,3,4,5,6,7] → [1,1,2,2,3,3,4,4,5,5,6,6,7,7]
 ðý       # Join this list by spaces
          #  i.e. [1,1,2,2,3,3,4,4,5,5,6,6,7,7] → '1 1 2 2 3 3 4 4 5 5 6 6 7 7'
   ¹v     # Loop `y` over the input-List:
     yõ.; # Replace every first occurrence of `y` with an empty string
          #  i.e. '1 1 2 2 3 3 4 4 5 5 6 6 7 7' and 3 → '1 1 2 2  3 4 4 5 5 6 6 7 7'

R , 59 55 bytes

Usando el vecsetspaquete podemos reducir la longitud de la respuesta. Con glpodemos obtener la salida ordenada. Esto no funciona en TIO. Siguiendo el estilo de @ digEmAll de solución (bastante inteligente) sin una definición de función, esto puede considerarse una solución de 55 bytes.

vecsets::vsetdiff(c(gl(m<-max(L<-scan()),sum(L==m))),L)

f=function(x){scan<-function()x
vecsets::vsetdiff(c(gl(m<-max(L<-scan()),sum(L==m))),L)
}

f(c(1))                # expected: integer(0)
f(c(7))                # expected: c(1, 2, 3, 4, 5, 6)
f(c(1, 1, 1))          # expected: integer(0)
f(c(1, 8))             # expected: c(2, 3, 4, 5, 6, 7)
f(c(3, 3, 3, 3))       # expected: c(1, 1, 1, 1, 2, 2, 2, 2)
f(c(5, 2, 4, 5, 2))    # expected: c(1, 1, 3, 3, 4)
f(c(5, 2, 4, 5, 5))    # expected: c(1, 1, 1, 2, 2, 3, 3, 3, 4, 4)

JavaScript (ES6), 98 bytes

Esto resultó ser bastante difícil de jugar por debajo de los 100 bytes. Puede haber un mejor enfoque.

a=>(a.map(o=M=m=n=>m=(c=o[M=n<M?M:n,n]=-~o[n])<m?m:c),g=k=>k?o[k]^m?[...g(k,o(k)),k]:g(k-1):[])(M)

Pruébalo en línea!

¿Cómo?

Primero recorremos la matriz de entrada a[]para recopilar los siguientes datos:

• M = elemento más alto encontrado en la matriz de entrada
• m = mayor número de ocurrencias del mismo elemento
• o[n] = número de ocurrencias de n

Tenga en cuenta que ose define principalmente como una función, pero el objeto subyacente también se utiliza para almacenar el número de ocurrencias.

a.map(                      // a[] = input array()
  o =                       // o = callback function of map()
  M = m =                   // initialize m and M to non-numeric values
  n =>                      // for each value n in a[]:
    m = (                   //   this code block will eventually update m
      c = o[                //     c = updated value of o[n]
        M = n < M ? M : n,  //     update M to max(M, n)
        n                   //     actual index into o[]
      ] = -~o[n]            //     increment o[n]
    ) < m ?                 //   if o[n] is less than m:
      m                     //     let m unchanged
    :                       //   else:
      c                     //     set it to c
)                           // end of map()

Luego usamos la función recursiva g()para construir la salida.

(g = k =>                   // k = current value
  k ?                       // if k is not equal to 0:
    o[k] ^ m ?              //   if o[k] is not equal to m:
      [ ...g(k, o(k)),      //     increment o[k] and do a recursive call with k unchanged
        k ]                 //     append k to the output
    :                       //   else:
      g(k - 1)              //     do a recursive call with k - 1
  :                         // else:
    []                      //   stop recursion
)(M)                        // initial call to g() with k = M

Haskell, 72 bytes

import Data.List
f l=(last(sortOn(0<$)$group$sort l)>>[1..maximum l])\\l

Pruébalo en línea!

            sort l      -- sort input list
       group            -- group identical elements
   sortOn(0<$)          -- sort by length
 last                   -- take the last element, i.e. the list
                        -- of the most common element
      >>[1..maximum l]  -- replace each of it's elements
                        -- with the list [1..maximum l]
  \\l                   -- remove elements of the input list

Brachylog , 18 17 bytes

⌉⟦₁;Ij₎R⊇p?;.cpR∧

Pruébalo en línea!

Guardado 1 byte gracias a @Kroppeb.

Explicación

⌉                  Take the largest element in the Input
 ⟦₁                 Construct the range [1, …, largest element in the Input]
   ;Ij₎R            Juxtapose that range to itself I times, I being unknown; 
                       call the result R
       R⊇p?         The Input must be an ordered subset of R, up to a permutation
          ?;.c      Concatenate the Input and the Output 
                       (the Output being unknown at this point)
              pR    This concatenation must result in R, up to a permutation
                ∧   (Find a fitting value for the Output that verifies all of this)

Java 10, 186 bytes

import java.util.*;L->{Integer m=0,f=0,t;for(int i:L){m=i>m?i:m;f=(t=Collections.frequency(L,i))>f?t:f;}var r=new Stack();for(;m>0;m--)for(t=f;t-->0;)if(!L.remove(m))r.add(m);return r;}

Pruébalo en línea.

Explicación:

import java.util.*;   // Required import for Collections and Stack
L->{                  // Method with Integer-list as both parameter and return-type
  Integer m=0,        //  Max, starting at 0
          f=0,        //  Max frequency, starting at 0
          t;          //  Temp integer
  for(int i:L){       //  Loop over the input-List
    m=i>m?i:m;        //   If the current item is larger than the max, set it as new max
    f=(t=Collections.frequency(L,i))>f?t:f;}
                      //   If the current frequency is larger than the max freq, set it as new max
  var r=new Stack();  //  Result-List
  for(;m>0;m--)       //  Loop the maximum in the range [m,0)
    for(t=f;t-->0;)   //   Inner loop the frequency amount of times
      if(!L.remove(m))//    Remove `m` from the input list
                      //    If we were unable to remove it:
        r.add(m);     //     Add it to the result-List
  return r;}          //  Return the result-List

Casco , 12 bytes

Guardado 1 byte gracias a BWO .

S-§*oḣ▲(▲Ṡm#

Pruébalo en línea!

MATL , 24 21 bytes

X>:GS&Y'X>yGhS&Y'q-Y"

Pruébalo en línea!

MATL , 14 bytes

La entrada es un vector de columna, con un ;separador.

llXQtn:yX>b-Y"

Pruébalo en línea! O verifique todos los casos de prueba (esto se muestra --después de cada salida para poder identificar la salida vacía).

Explicación

Considere la entrada [5; 2; 4; 5; 5]como un ejemplo.

llXQ     % Implicit input. Accumarray with sum. This counts occurrences
         % of each number, filling with zeros for numbers not present
         % STACK: [0; 1; 0; 1; 3]
tn:      % Duplicate, number of elements, range
         % STACK: [0; 1; 0; 1; 3], [1 2 3 4 5]
yX>      % Duplicate from below, maximum of array
         % STACK: [0; 1; 0; 1; 3], [1 2 3 4 5], 3 
b        % Bubble up
         % STACK: [1 2 3 4 5], 3, [0; 1; 0; 1; 3] 
-        % Subtract, element-wise
         % STACK: [1 2 3 4 5], [3; 2; 3; 2; 0] 
Y"       % Repelem (run-length decode). Implicit display
         % STACK: [1 1 1 2 2 3 3 3 4 4]

Pyth , 13 bytes

.-*SeSQeSlM.g

Pruébalo aquí! o echa un vistazo a una suite de prueba!

Carbón de leña , 19 bytes

Ｆ…·¹⌈θＥ⁻⌈Ｅθ№θκ№θιＩι

Pruébalo en línea! El enlace es a la versión detallada del código. Hubiera sido de 16 bytes si los enteros hubieran sido no negativos en lugar de positivos. Explicación:

     θ              First input
    ⌈               Maximum
 …·¹                Inclusive range starting at 1
Ｆ                   Loop over range
          θ         First input
         Ｅ          Loop over values
            θ       First input
             κ      Inner loop value
           №        Count occurrences
        ⌈           Maximum
               θ    First input
                ι   Outer loop value
              №     Count occurrences
       ⁻            Subtract
      Ｅ             Map over implicit range
                  ι Current value
                 Ｉ  Cast to string
                    Implicitly print on separate lines

APL (Dyalog Classic) , 18 17 bytes

∊{⊂⍳⌈/⍵}~¨∘↓∘⍉⊣¨⌸

Pruébalo en línea!

usos ⎕io←1

Prólogo (SWI) , 211 bytes

Ha pasado un tiempo desde que programé en Prolog. Definitivamente se puede jugar más golf, pero tengo un examen para estudiar jajaja.

Código

f(L,X):-max_list(L,M),f(L,M,[],X,M).
f([],0,_,[],_).
f(L,0,_,A,M):-f(L,M,[],A,M).
f([],I,H,[I|A],M):-N is I-1,f(H,N,[],A,M).
f([I|R],I,H,A,M):-append(H,R,S),f(S,I,[],[I|A],M).
f([H|R],I,G,A,M):-f(R,I,[H|G],A,M).

Pruébalo en línea!

Versión sin golf

f(List, Result) :- 
    max_list(List, MaxIndex), 
    f(List, MaxIndex, [], Result, MaxIndex).

f([], 0, _, [], _).

f(List, 0, _, Acc, MaxIndex) :- 
    f(List, MaxIndex, [], Acc, MaxIndex).

f([], Index, History, [Index | Acc], MaxIndex) :- 
    NewIndex is Index - 1, f(History, NewIndex, [], Acc, MaxIndex).

f([Index | Remaining], Index, History, Acc, MaxIndex) :-
    append(History, Remaining, Result),
    f(Result, Index, [], [Index | Acc], MaxIndex).

f([Head | Remaining], Index, History, Acc, MaxIndex) :- 
    f(Remaining, Index, [Head | History], Acc, MaxIndex).

Clojure, 94 bytes

#(for[F[(frequencies %)]i(range 1(+(apply max %)1))_(range(-(apply max(vals F))(or(F i)0)))]i)

C ++, 234 bytes

#include<vector>
#include<map>
using X=std::vector<int>;
X f(X x){int q,z;q=z=0;std::map<int,int>y;X o;
for(auto i:x)++y[i];for(auto i:y)q=q>i.second?q:i.second;
for(;++z<=y.rbegin()->first;)for(;y[z]++<q;)o.push_back(z);return o;}

(Las nuevas líneas en el cuerpo de la función son para facilitar la lectura).

La función toma y devuelve un vector de entradas. Utilizastd::map para encontrar el elemento máximo de la lista de entrada y también para contar las ocurrencias de cada elemento distinto.

Explicación:

// necessary includes. Note that each of these is longer than whole Jelly program!
#include <vector>
#include <map>

// this type occurs three times in the code
using X = std::vector<int>;

// The function
X f (X x)
{
   // initialize some variables
   int q, z; // q will hold the max count
   q = z = 0;
   std::map <int, int> y; // The map for sorting
   X o; // The output vector

   // Populate the map, effectively finding the max element and counts for all of them
   for (auto i : x)
       ++y[i];

   // find the max count
   for (auto i : y)
       q = q > i.second ? q : i.second;

   // Populate the output vector

   // Iterate all possible values from 1 to the max element (which is the key at y.rbegin ())
   // Note that z was initialized at 0, so we preincrement it when checking the condition
   for (; ++z <= y.rbegin ()->first;)
       // for each possible value, append the necessary quantity of it to the output
       for(; y[z]++ < q;)
           o.push_back (z);

   return o;
}

Gaia , 12 bytes

::⌉┅¤:C¦⌉&¤D

Pruébalo en línea!

C (gcc) , 177 bytes

La entrada y salida se realizan a través de stdin y stdout. Ambas matrices tienen un límite de 2 ^ 15 elementos, pero podrían ser tan grandes como 2 ^ 99 elementos.

f(j){int n=0,m=0,i=0,a[1<<15],b[1<<15]={0};for(;scanf("%i",&a[i])>0;i++)j=a[i],m=j>m?j:m,b[j-1]++;for(i=m;i--;)n=b[i]>n?b[i]:n;for(i=m;i--;)for(j=n-b[i];j--;)printf("%i ",i+1);}

Con algo de formato:

f(j){
  int n=0, m=0, i=0, a[1<<15], b[1<<15]={0};
  for(;scanf("%i",&a[i])>0;i++) j=a[i], m=j>m?j:m, b[j-1]++;
  for(i=m;i--;) n=b[i]>n?b[i]:n;
  for(i=m;i--;) for(j=n-b[i];j--;) printf("%i ",i+1);
}

Pruébalo en línea!