Eingang

Eine Liste nichtnegativer Ganzzahlen.

Ausgabe

Die größte nichtnegative Ganzzahl h, sodass mindestens eine hder Zahlen in der Liste größer oder gleich ist h.

Testfälle

[0,0,0,0] -> 0
[12,312,33,12] -> 4
[1,2,3,4,5,6,7] -> 4
[22,33,1,2,4] -> 3
[1000,2,2,2] -> 2
[23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42] -> 20

Regeln

Sie können entweder ein vollständiges Programm oder eine Funktion schreiben, und auch anonyme Funktionen sind zulässig. Dies ist Code-Golf, so dass die wenigsten Bytes gewinnen. Standardlücken sind nicht zulässig.

Hintergrund

Der h-Index ist ein Begriff, der im akademischen Bereich verwendet wird, um die Wirkung und Produktivität eines Forschers zu erfassen. Laut Wikipedia hat ein Forscher den Index h , wenn er h wissenschaftliche Artikel veröffentlicht hat, von denen jeder mindestens h mal in anderen Artikeln zitiert wurde. Bei dieser Herausforderung geht es also darum, den h-Index aus einer Liste von Zitationszählungen zu berechnen.

Aktualisieren

Wow, rundum tolle Antworten! Ich habe die kürzeste angenommen, aber wenn jemand anderes eine noch kürzere findet, aktualisiere ich meine Auswahl entsprechend.

Gewinner nach Sprache

Hier ist eine Preisträgertabelle nach Sprachen, die ich ebenfalls auf dem Laufenden halten möchte. Ich habe alle Beiträge mit nicht negativer Punktzahl aufgenommen. Bitte korrigieren Sie mich, wenn ich hier einen Fehler gemacht habe.

• APL : 7 Bytes von @MorisZucca
• Bash + Coreutils : 29 Bytes von @DigitalTrauma
• C # : 103 Bytes von @ LegionMammal978
• C ++ : 219 Bytes von @ user9587
• CJam : 15 Bytes von @nutki
• GolfScript : 13 Bytes von @IlmariKaronen
• Haskell : 40 Bytes von @proudhaskeller
• J : 12 Bytes von @ ɐɔıɐɔuʇǝɥʇs
• Java : 107 Bytes von @Ypnypn
• JavaScript : 48 Bytes von @ edc65
• Mathematica : 38 Bytes von @ kukac67
• Perl : 32 Bytes von @nutki
• Pyth : 10 Bytes von @isaacg
• Python : 49 Bytes von @feersum
• R : 29 Bytes von @MickyT
• Ruby : 41 Bytes von @daniero
• Scala : 62 Bytes von @ChadRetz
• SQL : 83 Bytes von @MickyT
• TI-BASIC : 22 Bytes von @Timtech

APL 7

+/⊢≥⍋∘⍒

Kann online auf tryapl.org ausprobiert werden

f←+/⊢≥⍋∘⍒
f¨(4⍴0)(12 312 33 12)(⍳7)(22 33 1 2 4)(1000 2 2 2)(23 42 12 92 39 46 23 56 31 12 43 23 54 23 56 73 35 73 42 12 10 15 35 23 12 42)
0 4 4 3 2 20

Python, 52

f=lambda s,n=0:n<sum(n<x for x in s)and f(s,n+1)or n

Eine rekursive Lösung. Führen Sie dies in Stackless Python aus, wenn Sie sich Sorgen über Überläufe machen.

n=0Überprüft ab , ob mindestens eine n+1der Nummern vorhanden ist n+1. Wenn ja, wird erhöht nund erneut gestartet . Wenn nicht, Ausgänge n.

Die Bedingung wird mithilfe von Pythons Kurzschluss für Boolesche Werte erfüllt. Der Ausdruck sum(n<x for x in s)zählt die Anzahl der Werte s, die größer sind als ndurch Hinzufügen der Indikator-Booleschen Werte, die als 0oder behandelt werden 1.

Zum Vergleich ist das iterative Äquivalent 2 Zeichen länger. Es erfordert Python 2.

s=input()
n=0
while n<sum(n<x for x in s):n+=1
print n

Leider muss die Eingabe für eine Variable gespeichert werden, bevor sie wiederholt werden kann. Andernfalls versucht Python, die Eingabe wiederholt zu lesen.

Pyth, 13 10 Bytes

tf<l-QUTT1

Eingabe in einer Form wie [22,33,1,2,4]STDIN.

Probieren Sie es hier aus.

Wie es funktioniert:

-QUTist , alle Zahlen in dem Eingang ( Q) mindestens so groß wie die Zahl ist , überprüft, T.

<l-QUTTist wahr, wenn die Länge dieser Liste kleiner als ist T.

f<l-QUTT1Findet die erste Ganzzahl, die für den inneren Check true zurückgibt, beginnend bei 1und aufsteigend.

tf<l-QUTT1 dekrementiert dies um eins und gibt den größten Wert an, für den die Bedingung falsch ist, dh den h-Index.

Ab 1 wird sichergestellt, dass 0zurückgegeben wird, wenn der Test immer wahr ist, wie im ersten Testfall.

Python 2, 49

Die Eingabe sollte im gleichen Format wie in den Beispielen erfolgen.

i=0
for z in sorted(input())[::-1]:i+=z>i
print i

CJam, 15 Bytes

Direkte Übersetzung meiner Perl-Lösung.

l~{~}${W):W>},,

J ( 13-12 )

[:+/i.@#<\:~

Ziemlich ähnlich zu Randomra's Lösung. Demonstration:

   f=:[:+/i.@:#<\:~
   f 0,0,0,0
0
   f 12,312,33,12
4
   f 1,2,3,4,5,6,7
4
   f 22,33,1,2,4
3
   f 1000,2,2,2
2
   f 23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42
20

Mathematica, 44 42 40 38 Bytes

Anonyme Funktion:

LengthWhile[i=0;SortBy[#,-#&],#>i++&]&

Führen Sie es aus, indem Sie die Eingabe wie folgt bis zum Ende anheften:

In: LengthWhile[i=0;SortBy[#,-#&],#>i++&]&@{1,2,3,4,5,6,7}
Out: 4

SQL, 81 94 83

Bei einer Tabelle (I) von Werten (V) gibt die folgende Abfrage h zurück. Getestet in PostgreSQL und funktioniert auch in SQL Server. Bearbeiten Geben Sie 0 anstelle von NULL zurück. Besser gemacht mit einem COUNT, danke @nutki

SELECT COUNT(R)FROM(SELECT ROW_NUMBER()OVER(ORDER BY V DESC)R,V FROM I)A WHERE R<=V

SQLFiddle- Beispiel

Im Wesentlichen werden die Zeilen in absteigender Reihenfolge der Werte nummeriert. Dann wird die maximale Zeilennummer zurückgegeben, wobei die Zeilennummer größer als der Wert ist.

R 39 35 29

s=sort(i);sum(s>=length(s):1)

Wenn ein Vektor von ganzen Zahlen in i gegeben ist und die Logik einer umgekehrten Sortierung verwendet wird, wird die Länge des Vektors zurückgegeben, wobei die Elementnummer kleiner als s ist. Danke an @plannapus für den netten Tipp.

> i=c(23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42)
> s=sort(i);length(s[s>=length(s):1])
[1] 20
> i=c(0,0,0,0)
> s=sort(i);length(s[s>=length(s):1])
[1] 0

CJam, 23 Bytes

l~:I,),W%{_If>:!:+>}$0=

Dies nimmt die Liste als Array auf STDIN, wie

[23 42 12 92 39 46 23 56 31 12 43 23 54 23 56 73 35 73 42 12 10 15 35 23 12 42]

Teste es hier.

Damit können Sie alle Testfälle ausführen:

[0 0 0 0]
[12 312 33 12]
[1 2 3 4 5 6 7]
[22 33 1 2 4]
[1000 2 2 2]
[23 42 12 92 39 46 23 56 31 12 43 23 54 23 56 73 35 73 42 12 10 15 35 23 12 42]]
{:I,),W%{_If>:!:+>}$0=N}/

Erläuterung

l~:I,),W%{_If>:!:+>}$0=
l~:I                    "Read input, evaluate, store in I.";
    ,                   "Get length of input N.";
     ),W%               "Create range from 0 to N, reverse.";
         {         }$   "Sort stably.";
          _I            "Duplicate candidate h, push input list.";
            f>          "Map each number to 1 if it's less or 0 otherwise.";
              :!        "Invert all results.";
                :+      "Sum them up.";
                  >     "Check if the sum is less than the candidate h.";
                     0= "Pick the first element.";

Die Logik ist ein bisschen rückwärts, hat aber ein paar Bytes gespart. Grundsätzlich wird der Block zum Sortieren von Rückgaben 0für gültige Kandidaten und 1ansonsten übergeben. Die gültigen Kandidaten stehen also im sortierten Array an erster Stelle. Und da die Sortierung stabil ist und wir mit einer Liste von N bis 1 beginnen, gibt dies das größte gültige h zurück.

Perl 5: 32 (30 + 2 für -pa)

#!perl -pa
$_=grep$_>$i++,sort{$b<=>$a}@F

Übernimmt eine durch Leerzeichen getrennte Eingabe in STDIN:

perl hidx.pl <<<'1 2 3 4 5 6 7'

Python (63)

Grundsätzlich ein direkter Port meiner J-Lösung. Offensichtlich viel länger, wie man sich vorstellen kann.

lambda x:sum(a>b for a,b in zip(sorted(x)[::-1],range(len(x))))

Haskell, 40

f s=[x-1|x<-[1..],x>sum[1|r<-s,r>=x]]!!0

Dadurch wird nach der ersten Zahl gesucht, die nicht zum Schema passt, und der Vorgänger wird zurückgegeben.

Ruby 44 41

Rekursive, mehr oder weniger gleiche Strategie wie die Python-Lösung von xnor:

f=->a,n=0{a.count{|x|x>n}<n+1?n:f[a,n+1]}

Ruby 52

Nicht rekursiv:

f=->a{a.size.downto(0).find{|x|a.count{|y|y>=x}>=x}}

"Stabby" Lambda / anonyme Funktionen erfordern Ruby 1.9 oder neuer. Rufen Sie mit zBf[[22,33,1,2,4]]

Bash + Coreutils, 29

sort -nr|nl -s\>|bc|grep -c 0

Eingabe von stdin als durch Zeilenumbrüche getrennte Liste.

• sort die ganzen Zahlen in absteigender Reihenfolge
• nl Stellt jeder Zeile eine 1-basierte Zeilennummer voran, wobei die Zeilennummer und der Rest der Zeile durch ein Größer-als-Zeichen getrennt werden >
• Berechnen Sie jede Zeile mit bc. Ganzzahlen, die kleiner als ihre Zeilennummer sind, ergeben 0. Sonst 1.
• grepzählt die Anzahl von 0s, dh die Anzahl von ganzen Zahlen größer oder gleichh

Beispiel

$ for i in {23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42}; do echo $i; done | ./atleasth.sh
20
$ for i in {1,2,3,4,5,6,7}; do echo $i; done | ./atleasth.sh
4
$ 

JavaScript (ES6) 48

Rekursive Lösung.

F=(l,h=-1)=>l.filter(v=>v>h).length>h?F(l,h+1):h

Test in der FireFox / FireBug-Konsole

;[
  [0,0,0,0],
  [12,312,33,12],
  [1,2,3,4,5,6,7],
  [22,33,1,2,4],
  [1000,2,2,2],
  [23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42]
 ].forEach(l=>console.log(l,F(l)))

Ausgabe

[0, 0, 0, 0] 0
[12, 312, 33, 12] 4
[1, 2, 3, 4, 5, 6, 7] 4
[22, 33, 1, 2, 4] 3
[1000, 2, 2, 2] 2
[23, 42, 12, 92, 39, 46, 23, 56, 31, 12, 43, 23, 54, 23, 56, 73, 35, 73, 42, 12, 10, 15, 35, 23, 12, 42] 20

Java 8, 116 Bytes.

Volle Klasse:

import java.util.*;
import java.util.stream.*;

class H{

    public static void main(String[]a){
        System.out.println(new H().f(Stream.of(a[0].split(",")).mapToInt(Integer::parseInt).toArray()));
    }

    int i;

    int f(int[]n){
        Arrays.sort(n);
        i=n.length;
        Arrays.stream(n).forEach(a->i-=a<i?1:0);
        return i;
    }
}

Funktion:

import java.util.*;int i;int f(int[]n){Arrays.sort(n);i=n.length;Arrays.stream(n).forEach(a->i-=a<i?1:0);return i;}}

APL, 12 Zeichen

(+/⊢≥⍒)⊂∘⍒⌷⊢

C ++ 815 219 von (wc -c main.cpp)

Okay, hier ist der schlechteste Code, den ich je geschrieben habe! :)

#include <iostream>
#include <list>
using namespace std;int main(int c,char** v){list<int>n(--c);int h=c;for(int&m:n)m=atoi(*(v+(h--)));n.sort();for(auto r=n.rbegin();r!=n.rend()&&*r++>++h;);cout<<(h==c?h:--h)<<endl;}

Gelee, 6 Bytes

NỤỤ<’S

Erläuterung:

N           Negate (so that repeated elements won't mess up the second grade down)
 Ụ          Grade down
  Ụ         Twice.
   <’       Predicate, check for each element if the new one (after grading) is lower than original array (minus 1 on each element)
     S      Sum

CJam, 22 Bytes

q~:Q,),{Q{1$>},,>!},W=

Nimmt die Liste als Eingabe:

[23 42 12 92 39 46 23 56 31 12 43 23  54 23 56 73 35 73 42 12 10 15 35 23 12 42]

Ausgabe:

20

Probieren Sie es hier aus

GolfScript, 13 Bytes

$-1%0\{1$>+}/

Testen Sie diesen Code online. ¹

Übernimmt die Eingabe als Array auf dem Stapel. Verwendet denselben Algorithmus wie die Python-Lösung von feersum , wobei die Zahlen im Array durchlaufen werden und ein Zähler von 0 erhöht wird, bis er dem aktuellen Element des Arrays entspricht oder dieses überschreitet.

^{1) Der Online-GolfScript-Server scheint wieder zufällige Timeouts zu haben. Wenn das Programm eine Zeitüberschreitung aufweist, führen Sie es erneut aus.}

TI-BASIC, 22 Bytes

ASCII-Darstellung:

Input L1:1:While Ans≤sum(Ans≥L1:Ans+1:End:Ans

Hex-Dump:

DC 5D 00 3E 31 3E D1 72 6D B6 72 6C 5D 00 3E 72 70 31 3E D4 3E 72

Ruft eine Liste als Eingabe ab. Überprüft ab Ans = 0, ob mindestens Ans + 1 der Nummern mindestens Ans + 1 sind. In diesem Fall wird Ans inkrementiert und die Schleife erneut ausgeführt. Wenn nicht, wird Ans ausgegeben.

JAGL Alpha 1.2 - 14

Zählt nicht, weil die C-Reverse-Array-Funktionalität nach der Frage hinzugefügt wurde, aber ich antworte trotzdem zum Spaß.

Nimmt an, dass das Array das erste Element auf dem Stapel ist und die Antwort oben auf dem Stapel platziert.

0SJC{Sd@>+1}/S

Zum Drucken fügen Sie einfach Pam Ende ein Byte hinzu.

Erläuterung:

0               Push the number 0 (the counter)
 SJC            Swap to array, sort and reverse
    {Sd@>+1}/   For each item in the array, add 1 to counter if counter is less than item
             S  Swap counter to top of stack

J, 15 11 Zeichen

(Derzeit kürzeste J-Lösung.)

   [:+/#\<:\:~

   ([:+/#\<:\:~) 1 2 3 4 5 6 7
4

Vergleicht <:sortierte Listenelemente \:~mit 1..n + 1 #\und zählt echte Vergleiche +/.

Testen der Ähnlichkeit mit anderen J-Lösungen in 100 zufälligen Testfällen:

   */ (([:+/#\<:\:~) = ([:+/i.@#<\:~))"1 ?100 100$100
1

Reng v.3.2, 43 Bytes

1#xk#yaïí'1ø ~n-1$\
1+)x(%:1,%1ex+y1-?^#y#x

Probieren Sie es hier aus! Dieser Code kann in drei Teile unterteilt werden: anfänglich, rechnerisch und endgültig.

Initiale

1#xk#yaïí'1ø

Speichert 1zu x, die Länge des Eingangsstapel kzu yund erhält alle Eingang ( aïí) , die dann (sortiert wird '). 1øgeht zur nächsten Zeile, dh zum nächsten Teil.

Computational

1+)x(%:1,%1ex+y1-?^#y#x

Reng hat keine eingebaute Ungleichung. Daher muss ein Algorithmus implementiert werden. Der kürzeste Algorithmus, den ich gefunden habe, a < bist %:1,%1e; das sieht so aus:

Command | Stack
  ---   | a, b
   %    | a/b
   :    | a/b, a/b
   1    | a/b, a/b, 1
   ,    | a/b, (a/b)%1
   e    | (a/b) == ((a/b)%1)

Ich bin sicher , das hat es geklärt! Lassen Sie mich weiter erklären. x % 1, dh Modul mit 1, bildet xauf ab (-1,1). Wir wissen , dass (a/b) % 1ist , a/bwenn a < b. Somit ist dieser Ausdruck gleich a < b.

Dies funktioniert jedoch aufgrund von Modulproblemen mit Null nicht ganz so gut. Also erhöhen wir zunächst jedes Mitglied des Stapels und des Zählers.

Nachdem wir den Ungleichungs-Booleschen Wert auf dem Stapel erhalten haben, x+addieren wir ihn zu x , belassen ihn jedoch für den Moment auf dem Stapel. y1-dekrementiert yund ?^steigt iff y == 0und wir gehen in die letzte Phase. Ansonsten setzen wir y-1in yund das Neue xin x.

Finale

             ~n-1$\

Dadurch wird das Residuum y-1aus dem Stapel entfernt, das Ergebnis dekrementiert, ausgegeben und das Programm beendet.

05AB1E , 5 Bytes

{Rā@O

Probieren Sie es online! oder als Test Suite

Erläuterung

{R      # sort descending
  ā@    # check each element if it's greater than or equal to its 1-based index
    O   # sum

Mathematica, 57 Bytes

FirstCase[Range[Length@#,0,-1],h_/;Count[#,k_/;k>=h]>=h]&

Dies ist eine anonyme Funktion, die eine Liste erstellt und eine Ganzzahl wie folgt zurückgibt

FirstCase[Range[Length@#,0,-1],h_/;Count[#,k_/;k>=h]>=h]&@{1,2,3,4,5,6,7}

Verwenden Sie dies, um alle Testfälle zu überprüfen:

FirstCase[Range[Length@#,0,-1],h_/;Count[#,k_/;k>=h]>=h]& /@ {
  {0, 0, 0, 0},
  {12, 312, 33, 12},
  {1, 2, 3, 4, 5, 6, 7},
  {22, 33, 1, 2, 4},
  {1000, 2, 2, 2},
  {23, 42, 12, 92, 39, 46, 23, 56, 31, 12, 43, 23, 54, 23, 56, 73, 35,
    73, 42, 12, 10, 15, 35, 23, 12, 42}
}

C # 103

Anonyme Funktion.

a=>{try{return a.OrderBy(b=>-b).Select((b,c)=>new{b,c}).First(b=>b.b<b.c+1).c;}catch{return a.Length;}}

Eingerückt:

a =>
{
    try
    {
        return a.OrderBy(b => -b).Select((b, c) => new { b, c }).First(b => b.b < b.c + 1);
    }
    catch
    {
        return a.Length;
    }
}

Scala, 62

def h(a:Int*)=Range(a.size,-1,-1).find(b=>a.count(b<=)>=b).get