Exécution du deuxième maximum d'une liste

20

Étant donné une liste d'entiers, votre tâche consiste à générer la deuxième valeur la plus élevée dans les premiers k éléments, pour chaque k compris entre 2 et la longueur de la liste d'entrée.

En d'autres termes, sortez la deuxième plus grande valeur pour chaque préfixe de l'entrée.

Vous pouvez sortir une valeur arbitraire pour le premier élément (où k = 1), ou simplement omettre cette valeur, car il n'y a pas de deuxième maximum pour une liste de 1 élément. Vous pouvez supposer qu'il y a au moins 2 éléments dans l'entrée.

Le code le plus court gagne.

Exemples

Input:
1 5 2 3 5 9 5 8
Output:
  1 2 3 5 5 5 8
Input:
1 1 2 2 3 3 4
Output:
  1 1 2 2 3 3
Input:
2 1 0 -1 0 1 2
Output:
  1 1 1 1 1 2
jimmy23013
la source
Mon anglais n'est pas le meilleur, comment est-il kdéterminé?
LiefdeWen
@LiefdeWen Affiche une liste contenant la réponse pour chaque k.
jimmy23013
2
1n'est pas, à proprement parler, la deuxième plus grande valeur de 1,1(2e exemple), c'est la deuxième valeur lorsqu'elle est triée décroissante.
Jonathan Allan
Peut-être que je suis juste stupide (même si je soupçonne que je pourrais vraiment commencer le week-end ..), mais je ne sais toujours pas comment cela fonctionne. Quelqu'un pourrait ELI5 le dernier cas de test pour moi? Les deux premiers cas de test que je peux résoudre en faisant simplement une boucle sur la liste, en déterminant le minimum actuel de la liste, puis supprimez cet élément (ou plus simple: triez la liste et supprimez le dernier élément). Il donne les résultats corrects pour les deux premiers cas de test, mais est manifestement faux (et donnera -1, 0, 0, 1, 1, 2pour le dernier cas de test.)
Kevin Cruijssen
1
@KevinCruijssen Rappelez-vous les deux plus grands nombres que vous avez vus. Dans le dernier cas, vous commencez avec 2 étant le plus grand, et ne sortez rien / peu importe car cela n'a pas de sens à ce stade. Ensuite, vous changez en 1 et 2 à la prochaine itération, vous produisez donc 1. Cela reste le même jusqu'à ce que vous atteigniez le 2 à la fin, puis vous avez 2 et 2 comme le plus grand et le deuxième plus grand
FryAmTheEggman

Réponses:

6

05AB1E , 5 octets

ηεà\à

Essayez-le en ligne!

Renvoie [](valeur arbitraire) pour le premier.

Erik le Outgolfer
la source
η¦ε{¨θdevrait fonctionner pendant 6 octets
Adnan
@Adnan Bien sûr> _ <a quand même trouvé un meilleur moyen ...
Erik the Outgolfer
Intéressant ... Z©KZ®‚¹sÃc'était ce que je pensais, je ne savais àmême pas que c'était une chose!
Magic Octopus Urn
Trouvé une autre alternative de 5 octets . J'ai utilisé à la Áθplace.
M. Xcoder
5

Husk , 9 7 octets

Sauvegardé un octet ou deux grâce à @Zgarb

mȯ→hOtḣ

Renvoie 0pour le premier "deuxième maximum"

Explication

         -- implicit input, e.g          [1,5,3,6]
      ḣ  -- prefixes                     [[],[1],[1,5],[1,5,3],[1,5,3,6]]
     t   -- remove the first element     [[1],[1,5],[1,5,3],[1,5,3,6]]
mȯ       -- map the composition of 3 functions
    O    --   sort                       [[1],[1,5],[1,3,5],[1,3,5,6]]
   h     --   drop the last element      [[],[1],[1,3],[1,3,5]
  →      --   return the last element    [0,1,3,5]
         -- implicit output

Essayez-le en ligne!

H.PWiz
la source
1
Vous pouvez mapper à la →hOplace et enregistrer un octet.
Zgarb
3

JavaScript (ES6), 58 51 50 octets

1 octet enregistré grâce à @Neil

Ajoute undefinedpour k = 1 .

a=>a.map(e=>(b=[e,...b]).sort((a,b)=>b-a)[1],b=[])

Cas de test

NB: Cet extrait utilise JSON.stringify()pour la lisibilité, qui - comme effet secondaire - se convertit undefineden null.

Arnauld
la source
1
Je pense qu'il a=>a.map(e=>(b=[e,...b]).sort((a,b)=>b-a)[1],b=[])n'a que 50 ans.
Neil
@Neil Nice. :-)
Arnauld
2

Pyth , 8 octets

m@Sd_2._

Essayez-le en ligne! ou Essayez la suite de tests!


Comment?

Cela génère le premier élément de la liste comme première valeur de la liste, conformément à la spécification. Vous pouvez générer une valeur arbitraire pour le premier élément .

m@Sd_2._ - Programme complet avec entrée implicite.

m ._Q - Mappe les préfixes de l'entrée avec une variable d.
  Sd - Trie le préfixe actuel.
 @ - Obtient l'élément ...
    _2 - À l'indice - 2 (le deuxième plus élevé).
           - Imprimer implicitement.
M. Xcoder
la source
2

Gelée , 8 octets

ḣJṢ€Ṗ€Ṫ€

Essayez-le en ligne!

La première valeur sera toujours 0 et les nombres suivants seront les seconds maximums de chaque préfixe.

Explication

ḣJṢ€Ṗ€Ṫ€  Input: array A
 J        Enumerate indices, [1, 2, ..., len(A)]
ḣ         Head, get that many values from the start for each, forms the prefixes
  Ṣ€      Sort each
    Ṗ€    Pop each, removes the maximum
      Ṫ€  Tail each
miles
la source
@ Challenger5 Je ne crois pas que cela fonctionne
miles
@ Challenger5 Cela ne fonctionne pas ...
Erik the Outgolfer
@EriktheOutgolfer Oh, d'accord.
Esolanging Fruit
2

Java (OpenJDK 8) , 87 86 octets

a->{int x,y=x=1<<-1;for(int c:a){if((c>x?x=c:c)>y){x=y;y=c;}System.out.print(x+" ");}}

Essayez-le en ligne!

Nevay
la source
+1 pour int x,y=x=. Je ne savais pas qu'une déclaration et une affectation distinctes pouvaient être faites dans la même déclaration.
Jakob
2

Python 2 , 45 octets

f=lambda l:l[1:]and f(l[:-1])+[sorted(l)[-2]]

Essayez-le en ligne!

Le côté droit du code est explicite. Cependant, que mettons-nous à gauche de la and? Parce que nous concaténons récursivement des parties d'une liste, nous avons besoin que le côté gauche soit vrai s'il la 2 éléments ou plus, et une liste vide sinon. l[1:]répond bien à ce critère.

Sisyphe
la source
1

Lot, 123 octets

@set/af=s=%1
@for %%n in (%*)do @call:c %%n
@exit/b
:c
@if %1 gtr %s% set s=%1
@if %1 gtr %f% set/as=f,f=%1
@echo %s%
Neil
la source
1

05AB1E , 5 octets

Trouvé un autre 5 octets, très différent de la solution d' Erik . La valeur arbitraire est le premier élément de la liste.

ηε{Áθ

Essayez-le en ligne!


Explication

ηε{Áθ  - Full program that reads implicitly from STDIN and outputs to STDOUT.

η      - Push the Prefixes of the list.
 ε     - Apply to each element (each prefix):
  {      - Sort the prefix list.
   Á     - Shift the list to the right by 1, such that the first element goes to the 
           beginning  and the second largest one becomes the last.
    θ    - Get the last element (i.e. the second largest)
         - Print implicitly.

Prenons un exemple, pour le rendre plus facile à comprendre.

  • D'abord, nous obtenons l'entrée implicite, disons que c'est [1, 5, 2, 3, 5, 9, 5, 8].

  • Ensuite, nous poussons ses préfixes en utilisant η- [[1], [1, 5], [1, 5, 2], [1, 5, 2, 3], [1, 5, 2, 3, 5], [1, 5, 2, 3, 5, 9], [1, 5, 2, 3, 5, 9, 5], [1, 5, 2, 3, 5, 9, 5, 8]].

  • Maintenant, le code mappe la liste et trie chaque préfixe à l'aide de {- [[1], [1, 5], [1, 2, 5], [1, 2, 3, 5], [1, 2, 3, 5, 5], [1, 2, 3, 5, 5, 9], [1, 2, 3, 5, 5, 5, 9], [1, 2, 3, 5, 5, 5, 8, 9]].

  • Nous prenons alors le dernier élément et le déplacer au début: [[1], [5, 1], [5, 1, 2], [5, 1, 2, 3], [5, 1, 2, 3, 5], [9, 1, 2, 3, 5, 5], [9, 1, 2, 3, 5, 5, 5], [9, 1, 2, 3, 5, 5, 5, 8]].

  • Bien sûr, maintenant le code obtient le dernier élément de chaque sous-liste en utilisant θ- [1, 1, 2, 3, 5, 5, 5, 8](le premier étant la valeur arbitraire.

M. Xcoder
la source
1

CJam , 16 octets

{_,,:)\f{<$-2=}}

Essayez-le en ligne!

Renvoie le premier élément pour le premier.

-2 grâce à Challenger5 .

Erik le Outgolfer
la source
{_,,:)\f{<$-2=}}est de deux octets plus court.
Esolanging Fruit
1

R , 54 49 octets

Merci à Giuseppe -5 octets. Je ne connaissais pas cette fonctionnalité de seq().

for(i in seq(x<-scan()))cat(sort(x[1:i],T)[2],"")

Essayez-le en ligne!

djhurio
la source
1
seq(x<-scan())est plus court de quelques octets.
Giuseppe
1

Japt , 12 10 octets

Le tableau de sortie se compose du premier élément du tableau d'entrée suivi de la séquence souhaitée.

£¯YÄ n< g1

Essaye-le


Explication

Entrée implicite du tableau U.

£

Carte sur U, où Yest l'index actuel.

¯YÄ

Tranche Ude 0à Y+1.

n<

Trier par ordre décroissant.

g1

Obtenez le deuxième élément.

Sortie implicite du tableau résultant.

Hirsute
la source
1

MATL , 19 10 octets

Merci à Luis Mendo d'avoir rasé 9 octets!

"GX@:)SP2)

Essayez-le ici .

Explication

"GX@:)SP2)
"                  for all the values in the input
 G                 get input
  X@:)             get values up to the iteration
      SP           sort it in descending order
        2)         get the second value
                   implicit end of loop and output
DanTheMan
la source
@LuisMendo Wow! Va montrer combien je sais sur MATL. Merci pour l'aide!
DanTheMan
1

J, 13 octets

_2&{@/:~ ::#\

Essayez-le en ligne! Le premier élément est toujours 1.

Explication

_2&{@/:~ ::#\
            \  Apply to prefixes
_2&{@/:~        Sort and take second-to-last atom
     /:~         Sort upwards
_2 {             Take second-to-last atom
         ::     If there's an error (i.e only one atom)
           #     Return the length of the list (1)

L'espace compte.

cole
la source
1

Ohm , 10 8 octets

-2 octets grâce à ETHproductions.

∙p»îS2~ª

Essayez-le en ligne!

Euh, c'est bizarre mais je ne sais pas comment pousser un nombre négatif ... Je ne sais pas vraiment Ohm. : P

totalement humain
la source
1
D'accord, cela 0 2-semble très étrange ...
M. Xcoder
1
Juste en regardant les documents (je ne sais rien sur Ohm), pourriez-vous faire 2~?
ETHproductions
@TEHProductions Oh, beaucoup mieux. Merci!
2017 totalement humain
0

Mathematica, 45 octets

Sort[s[[;;i]]][[-2]]~Table~{i,2,Length[s=#]}&

Essayez-le en ligne!

J42161217
la source
0

Swift 3 , 67 octets

func g(l:[Int]){print((1..<l.count).map{l[0...$0].sorted()[$0-1]})}

Suite de tests.

Swift 3 , 65 octets

{l in(1..<l.count).map{l[0...$0].sorted()[$0-1]}}as([Int])->[Int]

Suite de tests.


Comment les exécuter?

La première est une fonction complète qui prend l'entrée comme paramètre de fonction et imprime le résultat. Vous pouvez les utiliser exactement comme indiqué dans le lien de test. J'ai cependant décidé d'ajouter des instructions, car le deuxième type de fonction est très rarement utilisé et la plupart des gens ne connaissent même pas son existence. Usage:

g(l: [1, 1, 2, 2, 3, 3, 4] )

La seconde est une fonction anonyme, comme les lambdas. Vous pouvez l'utiliser exactement comme vous le feriez en Python, en déclarant une variable fet en l'appelant:

var f = {l in(1..<l.count).map{l[0...$0].sorted()[$0-1]}}as([Int])->[Int]

print(f([1, 1, 2, 2, 3, 3, 4]))

ou placez-le entre crochets et appelez-le directement ( (...)(ArrayGoesHere)):

print(({l in(1..<l.count).map{l[0...$0].sorted()[$0-1]}}as([Int])->[Int])([1, 1, 2, 2, 3, 3, 4]))
M. Xcoder
la source
0

PHP, 53 octets

for(;a&$n=$argv[++$i];rsort($a),print$a[1]._)$a[]=$n;

prend l'entrée des arguments de la ligne de commande. Sortie délimitée, plomb et traînée par semicola.
Courez avec -nrou essayez-le en ligne .

Donne un avertissement en PHP 7.1; remplacer a&par ""<pour corriger.
Ou utilisez for(;++$i<$argc;rsort($a),print$a[1]._)$a[]=$argv[$i];(54 octets)

Titus
la source
0

Mathematica 42 octets

Indépendamment arrivé à une réponse très similaire à @Jenny_mathy mais 3 octets plus court

Sort[#[[;;i]]][[-2]]~Table~{i,2,Length@#}&

Réalisé que le 1er max en cours d'exécution ne prend que 15 octets et deux appels de fonction!:

Max~FoldList~#&

Cela peut être fait de manière concise, car il Maxa les attributs Flatet OneIdentityce n'est pas vrai pour RankedMaxlequel serait le remplacement logique. Malheureusement, définir des attributs ou les modifier sur des fonctions existantes prend beaucoup trop d'octets, donc l'aplatissement doit être fait par d'autres moyens.

Tous les nèmes max en cours d'exécution peuvent être trouvés en 48 octets:

PadLeft[Sort/@Flatten/@FoldList[{##}&,{},#&@#]]&
Kelly Lowder
la source
0

k , 13 octets

{x(>x)1}'1_,\

Essayez-le en ligne!

           ,\ /sublists of increasing lengths (scan concat)
         1_   /remove the first sublist
{      }'     /for each sublist:
  (>x)        /    indices to permute sublist into largest to smallest
      1       /    get second index
 x            /    get sublist[that index]
zgrep
la source
0

Octave, 51 octets

@(a){[~,I]=cummax(a);a(I(2:end))=-inf;cummax(a)}{3}

- Une valeur arbitraire retournée pour le premier élément.

Essayez-le en ligne!

rahnema1
la source
0

JavaScript (ES6), 43 51 octets

Modifier: ajout de 8 octets car le tri numérique est souhaité. :(

a=>a.map((_,b)=>a.slice(0,b+1).sort((a,b)=>b-a)[1])

Garder celui-ci ici, cependant, car il est plus court à condition de vouloir un ordre lexicographique:

a=>a.map((_,b)=>a.slice(0,b+1).sort()[b-1])

Les deux expressions produisent undefinedpour le premier élément.

Code de test

Aaron Hill
la source
Notez que j'aurais préféré simplement commenter le post JS existant sans le système de réputation.
Aaron Hill du
Bienvenue chez PPCG! Je n'aime pas non plus le seuil de 50 commentaires, mais je suppose qu'ils en ont besoin pour empêcher les spammeurs de commenter. Quoi qu'il en soit, je pense que cela échouera si l'entrée contient un nombre à deux chiffres tel que 10, comme .sort()trie lexicographiquement par défaut (ie 1,10,100,11,12,13, ..., 2,20,21, ...). Vous devez inclure (a,b)=>a-bou similaire pour le trier par numéro.
ETHproductions
Merci, @ETHproductions. J'ai mis à jour pour la commande numérique, ce qui signifie que ce n'est plus suffisant. Tant pis.
Aaron Hill
0

Clojure, 56 octets

#(for[i(drop 2(reductions conj[]%))](nth(sort-by - i)1))

Il existe peut-être une meilleure façon de générer ces préfixes.

NikoNyrh
la source