Executando o segundo máximo de uma lista

20

Dada uma lista de números inteiros, sua tarefa é gerar o segundo maior valor nos primeiros k elementos, para cada k entre 2 e o comprimento da lista de entrada.

Em outras palavras, imprima o segundo maior valor para cada prefixo da entrada.

Você pode gerar um valor arbitrário para o primeiro elemento (onde k = 1) ou simplesmente omitir esse valor, pois não há um segundo máximo para uma lista de 1 elemento. Você pode assumir que há pelo menos 2 elementos na entrada.

O menor código vence.

Exemplos

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
fonte
Meu inglês não é o melhor, como é kdeterminado?
precisa saber é o seguinte
@LiefdeWen Produz uma lista contendo a resposta para cada k.
precisa saber é o seguinte
2
1estritamente falando, não é o segundo maior valor de 1,1(segundo exemplo); é o segundo valor quando classificado em ordem decrescente.
Jonathan Allan
Talvez eu seja apenas estúpido (embora eu suspeite que realmente possa ter começado o fim de semana ...), mas ainda não tenho certeza de como isso funciona. Alguém poderia ELI5 o último caso de teste para mim? Os dois primeiros casos de teste que eu posso resolver são apenas repetindo a lista, determinando o mínimo atual da lista e removendo esse item (ou mais fácil: classificar a lista e remover o último item). Ele dá os resultados corretos para os dois primeiros casos de teste, mas é obviamente errado (e vai dar -1, 0, 0, 1, 1, 2para o último caso de teste.)
Kevin Cruijssen
1
@KevinCruijssen Lembre-se dos dois maiores números que você já viu. No último caso, você começa com 2 sendo o maior e não produz nada / o que quer que seja, já que não faz sentido neste momento. Então você mudar para 1 e 2 na próxima iteração, para que a saída 1. Este permanece o mesmo até chegar a 2 no final, e então você tem 2 e 2 como a maior ea segunda maior
FryAmTheEggman

Respostas:

6

05AB1E , 5 bytes

ηεà\à

Experimente online!

Retorna [](valor arbitrário) para o primeiro.

Erik, o Outgolfer
fonte
η¦ε{¨θdeve funcionar para 6 bytes
Adnan
@Adnan Claro> _ <encontrou uma maneira melhor de qualquer maneira embora ...
Erik o Outgolfer
Interessante ... Z©KZ®‚¹sÃera o que eu estava pensando, nem sabia que àera uma coisa!
Magic Octopus Urn
Encontrei outra alternativa de 5 bytes . Eu usei em Áθvez disso.
Mr. Xcoder
5

Casca , 9 7 bytes

Salvo um ou dois bytes graças a @Zgarb

mȯ→hOtḣ

Retorna 0para o primeiro "segundo máximo"

Explicação

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

Experimente online!

H.PWiz
fonte
1
Você pode mapear →hOe salvar um byte.
Zgarb
3

JavaScript (ES6), 58 51 50 bytes

Guardado 1 byte graças a @Neil

Anexa undefinedpara k = 1 .

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

Casos de teste

Nota: este fragmento utiliza JSON.stringify()para facilitar a leitura, que - como efeito colateral - converte undefinedem null.

Arnauld
fonte
1
Eu acho que a=>a.map(e=>(b=[e,...b]).sort((a,b)=>b-a)[1],b=[])tem apenas 50 anos
Neil #
@ Neil Nice. :-)
Arnauld
2

Pitão , 8 bytes

m@Sd_2._

Experimente online! ou Experimente o Conjunto de Testes!


Quão?

Isso gera o primeiro elemento da lista como o primeiro valor da lista, conforme a especificação Você pode gerar um valor arbitrário para o primeiro elemento .

m@Sd_2._ - Programa completo com entrada implícita.

m ._Q - Mapeie os prefixos da entrada com uma variável d.
  Sd - classifica o prefixo atual.
 @ - Obtém o elemento ...
    _2 - No índice - 2 (o segundo mais alto).
           - Imprima implicitamente.
Mr. Xcoder
fonte
2

Gelatina , 8 bytes

ḣJṢ€Ṗ€Ṫ€

Experimente online!

O primeiro valor será 0, sempre, e os seguintes números serão os segundos máximos de cada prefixo.

Explicação

ḣ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
milhas
fonte
@ Challenger5 Eu não acredito que funcione
milhas
@ Challenger5 que não funciona ...
Erik o Outgolfer
@EriktheOutgolfer Oh, ok.
Esolanging Fruit
2

Java (OpenJDK 8) , 87 86 bytes

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+" ");}}

Experimente online!

Nevay
fonte
+1 para int x,y=x=. Eu não sabia que uma declaração e atribuição separadas poderiam ser feitas na mesma declaração.
Jakob
2

Python 2 , 45 bytes

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

Experimente online!

O lado direito do código é auto-explicativo. No entanto, o que colocamos à esquerda do and? Como estamos concatenando partes de uma lista recursivamente, precisamos que o lado esquerdo seja verdadeiro se ltiver 2 ou mais elementos e, caso contrário, uma lista vazia. l[1:]satisfaz bem esse critério.

Sísifo
fonte
1

Lote, 123 bytes

@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
fonte
1

05AB1E , 5 bytes

Encontrei outro 5-byter, muito diferente da solução de Erik . O valor arbitrário é o primeiro elemento da lista.

ηε{Áθ

Experimente online!


Explicação

ηε{Áθ  - 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.

Vamos dar um exemplo, para facilitar a compreensão.

  • Primeiro obtemos a entrada implícita, digamos que seja [1, 5, 2, 3, 5, 9, 5, 8].

  • Em seguida, pressionamos seus prefixos usando η- [[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]].

  • Agora, o código mapeia a lista e classifica cada prefixo usando {- [[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]].

  • Em seguida, tomar o último elemento e movê-lo para o início: [[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]].

  • Obviamente, agora o código obtém o último elemento de cada sub-lista usando θ- [1, 1, 2, 3, 5, 5, 5, 8](o primeiro é o valor arbitrário.

Mr. Xcoder
fonte
1

CJam , 16 bytes

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

Experimente online!

Retorna o primeiro elemento para o primeiro.

-2 graças a Challenger5 .

Erik, o Outgolfer
fonte
{_,,:)\f{<$-2=}}é dois bytes mais curto.
Esolanging Fruit
1

R , 54 49 bytes

Graças a Giuseppe -5 bytes. Eu não conhecia esse recurso seq().

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

Experimente online!

djhurio
fonte
1
seq(x<-scan())é mais curto em alguns bytes.
11557 Giuseppe
1

Japonês , 12 10 bytes

A matriz de saída consiste no primeiro elemento na matriz de entrada seguido pela sequência desejada.

£¯YÄ n< g1

Teste-o


Explicação

Entrada implícita da matriz U.

£

Mapa sobre U, onde Yestá o índice atual.

¯YÄ

Fatia Ude 0para Y+1.

n<

Classificar em ordem decrescente.

g1

Obtenha o segundo elemento.

Saída implícita da matriz resultante.

Shaggy
fonte
1

MATL , 19 10 bytes

Agradecimentos a Luis Mendo por remover 9 bytes!

"GX@:)SP2)

Experimente aqui .

Explicação

"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
fonte
@LuisMendo Wow! Mostra o quanto eu sei sobre MATL. Obrigado pela ajuda!
DanTheMan 12/08
1

J, 13 bytes

_2&{@/:~ ::#\

Experimente online!O primeiro elemento é sempre 1.

Explicação

_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)

O espaço é importante.

Cole
fonte
1

Ohm , 10 8 bytes

-2 bytes graças a ETHproductions.

∙p»îS2~ª

Experimente online!

Isso é estranho, mas eu não sei mais como enviar um número negativo ... Eu realmente não sei Ohm. : P

totalmente humano
fonte
1
Ok, 0 2-parece muito estranho ...
O Sr. Xcoder
1
Apenas olhando os documentos (não sei nada sobre Ohm), você poderia fazer 2~?
ETHproductions
@TEHProductions Oh, muito melhor. Obrigado!
totallyhuman
0

Mathematica, 45 bytes

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

Experimente online!

J42161217
fonte
0

Swift 3 , 67 bytes

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

Suíte de teste.

Swift 3 , 65 bytes

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

Suíte de teste.


Como executá-los?

A primeira é uma função completa que recebe a entrada como parâmetro de função e imprime o resultado. Você pode usá-los exatamente como mostrado no link de teste. Decidi adicionar instruções, porque o segundo tipo de função é usado muito raramente e a maioria das pessoas nem sabe de sua existência. Uso:

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

A segunda é uma função anônima, como lambdas. Você pode usá-lo exatamente como faria em Python, declarando uma variável fe chamando-a:

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 coloque-o entre colchetes e chame-o diretamente ( (...)(ArrayGoesHere)):

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

PHP, 53 bytes

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

recebe entrada dos argumentos da linha de comando. Saída delimitada, liderada e seguida por semicola.
Corra com -nrou experimente online .

Emite um aviso no PHP 7.1; substitua a&por ""<para corrigir.
Ou use for(;++$i<$argc;rsort($a),print$a[1]._)$a[]=$argv[$i];(54 bytes)

Titus
fonte
0

Mathematica 42 Bytes

Chegou independentemente a uma resposta muito semelhante a @Jenny_mathy, mas 3 bytes mais curto

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

Percebeu que o primeiro máximo em execução leva apenas 15 bytes e duas chamadas de função !:

Max~FoldList~#&

Isso pode ser feito de forma concisa, porque Maxtem os atributos Flate OneIdentitymas isso não é verdade paraRankedMax o que seria o substituto lógico. Infelizmente, definir atributos ou modificá-los em funções existentes ocupa muitos bytes, portanto, o nivelamento deve ser feito por outros meios.

Todos os enésimos enésimos máximos em execução podem ser encontrados em 48 bytes:

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

k , 13 bytes

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

Experimente online!

           ,\ /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
fonte
0

Oitava, 51 bytes

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

- Um valor arbitrário retornado para o primeiro elemento.

Experimente online!

rahnema1
fonte
0

JavaScript (ES6), 43 51 bytes

Edit: Adicionado 8 bytes desde que a classificação numérica é desejada. :(

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

Manter este aqui, porém, como é mais curto, desde que se queira uma ordem lexicográfica:

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

Ambas as expressões produzem undefinedpara o primeiro elemento.

Código de teste

Aaron Hill
fonte
Observe que eu preferiria simplesmente comentar sobre a postagem JS existente, se não fosse o sistema de reputação.
Aaron Hill
Bem-vindo ao PPCG! Também não gosto do limite de comentários de 50 representantes, mas acho que eles precisam para impedir que os spammers comentem. De qualquer forma, acho que isso falhará se a entrada contiver um número de dois dígitos, como 10, como .sort()padrão lexicograficamente (por exemplo, 1,10.100,11,12,13, ..., 2,20,21, ...). Você precisaria incluir (a,b)=>a-bou semelhante para classificá-lo por número.
ETHproductions
Obrigado, @ETHproductions. Atualizei para pedidos numéricos, o que significa que isso não é mais suficiente. Ah bem.
Aaron Hill
0

Clojure, 56 bytes

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

Talvez haja uma maneira melhor de gerar esses prefixos.

NikoNyrh
fonte