Trouver le plus grand nombre le plus proche

30

La tâche

Étant donné n'importe quel tableau d'entiers, par exemple:

[-1,476,578,27,0,1,-1,1,2]

et un index de ce tableau (cet exemple utilise une indexation basée sur 0 , mais vous pouvez également utiliser une indexation basée sur 1 ):

         index = 5
                 v
[-1,476,578,27,0,1,-1,1,2]

Retourne ensuite le nombre le plus proche supérieur à l'élément à cet index . Dans l'exemple, le nombre le plus proche supérieur à 1 est 27 (à 2 indices de distance).

         index = 5
                 v
[-1,476,578,27,0,1,-1,1,2]
            ^
Nearest greater number

Output = 27

Hypothèses

  • Le plus proche n'inclut pas l'emballage.
  • Le programme ne recevra jamais un tableau de longueur 1 (par exemple; [55]).
  • Vous devez supposer qu'il existe toujours un nombre supérieur à l'élément donné.
  • S'il y a 2 nombres supérieurs à l'élément à des distances égales, vous pouvez renvoyer l'un ou l'autre .

Paires d'E / S

Input:
Index = 45
Array = [69, 43, 89, 93, 62, 25, 4, 11, 115, 87, 174, 60, 84, 58, 28, 67, 71, 157, 47, 8, 33, 192, 187, 87, 175, 32, 135, 25, 137, 92, 183, 151, 147, 7, 133, 7, 41, 12, 96, 147, 9, 134, 197, 3, 107, 164, 90, 199, 21, 71, 77, 62, 190, 122, 33, 127, 185, 58, 92, 106, 26, 24, 56, 79, 71, 24, 24, 114, 17, 84, 121, 188, 6, 177, 114, 159, 159, 102, 50, 136, 47, 32, 1, 199, 74, 141, 125, 23, 118, 9, 12, 100, 94, 166, 12, 9, 179, 147, 149, 178, 90, 71, 141, 49, 74, 100, 199, 160, 120, 14, 195, 112, 176, 164, 68, 88, 108, 72, 124, 173, 155, 146, 193, 30, 2, 186, 102, 45, 147, 99, 178, 84, 83, 93, 153, 11, 171, 186, 157, 32, 90, 57, 181, 5, 157, 106, 20, 5, 194, 130, 100, 97, 3, 87, 116, 57, 125, 157, 190, 83, 148, 90, 44, 156, 167, 131, 100, 58, 139, 183, 53, 91, 151, 65, 121, 61, 40, 80, 40, 68, 73, 20, 135, 197, 124, 190, 108, 66, 21, 27, 147, 118, 192, 29, 193, 27, 155, 93, 33, 129]
Output = 199

Input:
Index = 2
Array = [4,-2,1,-3,5]
Output = 4 OR 5

Input:
Index = 0
Array = [2124, -173, -155, 146, 193, -30, 2, 186, 102, 4545]
Output = 4545

Input:
Index = 0
Array = [1,0,2,3]
Output = 2

Input:
Index = 2
Array = [3,-1,-3,-2,5]
Output = -1 OR -2
code-golf array-manipulation integer Graviton
la source
Pourriez-vous ajouter un cas de test dans lequel il recherche un résultat à gauche plutôt qu'à droite? soit1; [7,1,-4,2]
Kevin Cruijssen
Je pense que 2; [3,-1,-3,-2,5]c'est un joli cas de test. Il y a des chiffres positifs, mais le résultat est négatif.
Stewie Griffin
Puis-je utiliser 2 indexés?
Titus
@Titus, je veux dire si vous voulez vraiment
Graviton

Réponses:

7

MATL , 10 octets

yt&y)>fYk)

Cela utilise l'indexation basée sur 1. Essayez-le en ligne!

Explication

Tenez compte des entrées [4,-2,1,-3,5], à 3titre d'exemple.

y     % Take two inputs implicitly. Duplicate 2nd-top element in the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5]
t     % Duplicate top of the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], [4,-2,1,-3,5]
&y    % Duplicate 3rd-top element in the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], [4,-2,1,-3,5], 3
)     % Index: select elements from first input as indicated by second input
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], 1
>     % Greater than, element-wise
      % STACK: [4,-2,1,-3,5], 3, [1,0,0,0,1]
f     % Find: gives indices of non-zero entries
      % STACK: [4,-2,1,-3,5], 3, [1,5]
Yk    % Closest element: gives closest element of each entry in second input
      % ([1,5]) to each entry in the first input (3). In case of a tie it 
      % gives the left-most one
      % STACK: [4,-2,1,-3,5], 1
)     % Index: select elements from first input as indicated by second input
      % STACK: 4
      % Implicitly display
Luis Mendo
la source
2
Avez-vous une explication?
Nick Clifford
@NickClifford Bien sûr! J'attendais des éclaircissements sur le PO. Explication ajoutée
Luis Mendo
6

Gelée , 10 octets

ị<ṛTạ⁸$ÞḢị

Essayez-le en ligne!

Dennis
la source
Je jouais depuis des siècles en essayant de faire fonctionner le tri avec la valeur absolue :(
Jonathan Allan
5

Gelée , 11 12 octets

+1 octet - Aucun habillage autorisé.

Jạż⁸ṢZṪ»\Q2ị

1 indexé.

Essayez-le en ligne!

11 octets précédents (indexation enveloppante), indexés 0:

ṙżU$Fµ>ḢTḢị
Jonathan Allan
la source
Cela échoue par exemple 0 [1,0,2,3].
Ørjan Johansen
@ ØrjanJohansen Ah - il revient 3, ce qui est à 1 donc, euh, ouais "le plus proche" n'est pas défini ...
Jonathan Allan
1
J'ai demandé à OP d'ajouter ce cas de test.
Ørjan Johansen
4

JavaScript (ES6), 57 55 octets

Prend le tableau aet l'index idans la syntaxe de curry (a)(i).

a=>g=(i,p)=>(x=a[i-p])>a[i]||(x=a[i+p])>a[i]?x:g(i,-~p)

Cas de test

Afficher l'extrait de code

Arnauld
la source
Ne pouvez-vous pas utiliser à la |place de ||?
Neil
@Neil Non, nous ne voulons xpas être écrasés lorsque la première condition est remplie.
Arnauld
3

PHP, 106 octets

<?for($y=($a=$_GET[0])[$x=$_GET[1]];$y>=$a[$x-++$i]&&$y>=$a[$x+$i];);echo$y<$a[$x+$i]?$a[$x+$i]:$a[$x-$i];

Version en ligne

Jörg Hülsermann
la source
Il semble que ceux-ci ne fonctionnent pas pour le premier cas de test.
Nick Clifford
@NickClifford Maintenant, cela devrait fonctionner. J'ai une mauvaise approche
Jörg Hülsermann
3

Haskell , 48 octets

i%l=minimum[[j*j,x]|(j,x)<-zip[-i..]l,x>l!!i]!!1

Essayez-le en ligne! Cadre de test de Ørjan Johansen.

xnor
la source
Vous pouvez enregistrer un octet en utilisant une liste et à la !!1place (passez simplement Integerà Intdans l'en-tête).
Ørjan Johansen
@ ØrjanJohansen Merci, j'avais essayé et je ne savais pas pourquoi il se plaignait des types.
xnor
2

Assemblage x86-64, 40 octets

Inspiré de l'analyse de Johan du Toit et des solutions C de 2501 , ce qui suit est une fonction qui peut être assemblée avec MASM pour les plates-formes x86-64.

Il suit la convention d'appel Microsoft x64 pour la transmission des paramètres, donc la longueur totale du tableau est transmise ECX, la position d'intérêt est transmise EDXet le pointeur vers le tableau entier est transmis R8(c'est une plate-forme 64 bits, donc c'est un pointeur 64 bits).

Il renvoie le résultat (le "plus grand nombre le plus proche") dans EAX.

             FindNearestGreater PROC      
8B F2       \    mov     esi, edx     ; move pos parameter to preferred register
8B D9       |    mov     ebx, ecx     ; make copy of count (ecx == i; ebx == count)
            | MainLoop:
8B C6       |    mov     eax, esi     ; temp  = pos
2B C1       |    sub     eax, ecx     ; temp -= i
99          |    cdq
33 C2       |    xor     eax, edx
2B C2       |    sub     eax, edx     ; temp = AbsValue(temp)
            | 
41 8B 14 B0 |    mov     edx, DWORD PTR [r8+rsi*4]
41 39 14 88 |    cmp     DWORD PTR [r8+rcx*4], edx
7E 04       |    jle     KeepGoing    ; jump if (pValues[i] <= pValues[pos])
3B D8       |    cmp     ebx, eax
77 02       |    ja      Next         ; jump if (count > temp)
            | KeepGoing:
8B C3       |     mov     eax, ebx    ; temp = count
            | Next:
8B D8       |     mov     ebx, eax    ; count = temp
E2 E3       |     loop    MainLoop    ; equivalent to dec ecx + jnz, but smaller (and slower)
            | 
            |     ; Return pValues[temp + pos]
03 C6       |     add     eax, esi
41 8B 04 80 |     mov     eax, DWORD PTR [r8+rax*4]
C3          /     ret
             FindNearestGreater ENDP

Si vous vouliez l'appeler à partir du code C, le prototype serait:

extern int FindNearestGreater(unsigned int count,
                              unsigned int pos,
                              const    int *pValues);
Cody Grey
la source
1

Ruby , 64 octets

->a,i{a[(0...a.size).select{|j|a[j]>a[i]}.min_by{|j|(i-j).abs}]}

Essayez-le en ligne!

Encre de valeur
la source
1

Haskell , 53 octets

(#)prend un Intet une liste de Ints ou Integers (en fait n'importe quel Ordtype), et retourne un élément de la liste.

n#l=[x|i<-[1..],x:_<-(`drop`l)<$>[n-i,n+i],x>l!!n]!!0

Comment ça marche

  • nest l'indice donné et lest la liste / "tableau" donné.
  • i, prenant des valeurs à partir de 1, est la distance par rapport au ntest en cours.
  • Pour chacun i, nous vérifions les indices n-iet n+i.
  • xest l'élément d' lêtre testé. S'il réussit les tests, ce sera un élément de la compréhension de la liste résultante.
    • L'indexation d'index arbitraires avec !!pourrait donner une erreur hors limites, alors que droprenvoie à la place la liste entière ou une liste vide dans ce cas. La correspondance de modèle avec x:_vérifie que le résultat n'est pas vide.
    • x>l!!nteste que notre élément est supérieur à l'élément à index n(qui est garanti d'exister).
    • !!0 à la fin renvoie la première correspondance / élément de la compréhension de la liste.

Essayez-le en ligne!

Ørjan Johansen
la source
1

Brachylog , 17 octets

hH&∋₎<.&t:I≜+:H∋₍

Essayez-le en ligne!

Explication

hH                      Call the list H
  &∋₎<.                 Output is greater than the number at the specified index
       &t:I≜            Label I (0, then 1, then -1, then 2, then -2, …)
            +           Sum I with the input Index
             :H∋₍       Output is the element of H at index <the sum>
Fatalize
la source
1

Java (OpenJDK 8) , 98 octets

int f(int n,int[]a){for(int s=1,i=1,x=a[n];;n+=i++*s,s=-s)if(0<=n&n<a.length&&a[n]>x)return a[n];}

Essayez-le en ligne!

Vérifie les indices dans l'ordre spécifié par les sommes partielles de la somme suivante:

initial value + 1 - 2 + 3 - 4 + 5 - 6 + ...
Leaky Nun
la source
Je viens de lire la question et je voulais commencer à écrire une réponse .. Btw, pourquoi le s=1,et ,s=-s, cela n'a aucune utilité dans votre réponse .. Avez-vous oublié de le retirer d'une ancienne approche?
Kevin Cruijssen
1
@KevinCruijssen c'est une erreur et je la corrige maintenant. Il a réussi les tests car dans tous ces tests, le plus grand nombre le plus proche est à droite.
Leaky Nun
1

C, 69 octets

t;b;f(*d,c,p){for(b=c;c--;)d[c]>d[p]&(t=abs(p-c))<b?b=t:0;*d=d[p+b];}

Le premier argument est un argument d'entrée / sortie. La sortie est stockée dans son premier élément.

Voyez-le fonctionner en ligne .

2501
la source
1

R, 59 octets

function(l,i)l[j<-l>l[i]][which.min(abs(1:length(l)-i)[j])]

renvoie une fonction anonyme. Dans le cas où il y a deux éléments plus grands à égale distance, retournera le premier (indice moindre).

Essayez-le en ligne!

Giuseppe
la source
1

Pyth - 28 octets

JEehf>@T1@JQo@NZm(adQ@Jd)UlJ

Essayez-le

Maria
la source
1

PHP, 73 octets

function($i,$a){for(;$b<=$a[$i];)$b=max($a[++$d+$i],$a[$i-$d]);return$b;}

la fermeture prend l'index et le tableau basés sur 0 des arguments. Vérifiez tous les cas de test .

Titus
la source
Pas la prochaine valeur supérieure. Vous avez besoin d'une valeur avec la distance la plus basse qui est la plus élevée
Jörg Hülsermann
@ JörgHülsermann Merci de l'avoir signalé.
Titus
0

Pyth, 16 octets

JEh>#@JQ@LJaDQUJ

Suite de tests .

Leaky Nun
la source
0

C, 110 octets

c,o;e(g,l,f)int*g;{for(o=g[l],c=1;c<f;c++)l+c<f&&g[l+c]>o?o=g[l+c],c=f:0,l-c>=0&&g[l-c]>o?o=g[l-c],c=f:0;g=o;}

Essayez-le en ligne

Johan du Toit
la source
0

Java, 96 octets

int f(int n,int[]a){for(int s=1,i=1,x=a[n];0>(n+=i++*s)|n>=a.length||a[n]<=x;s=-s);return a[n];}

Les identifiants sont nommés comme la réponse de @Leaky Nun. De plus, la plupart des parties ont été alignées pour être fondamentalement les mêmes: En comparaison, le ifa été remplacé par la condition for-c (sacrifiant le point-virgule supplémentaire). Un deux-points a été supprimé en déplaçant increment-part dans la condition (donc les parenthèses de la précédente instruction if sont pratiquement "déplacées") - en changeant & en | n'a pas eu d'impact sur le nombre de personnages.

Johannes
la source
0

Clojure, 95 octets

#(%(nth(nth(sort-by first(for[i(range(count %)):when(>(% i)(% %2))][(Math/abs(- i %2))i]))0)1))

C'est le plus court que j'ai pu trouver :( J'ai aussi essayé de jouer avec ça mais je n'ai pas pu l'amener à la ligne d'arrivée:

#(map(fn[f c](f c))[reverse rest](split-at %2 %))
NikoNyrh
la source