python 3.2 - finden die zweite kleinsten Zahl in einer Liste mit Rekursion

So, ich muss die zweite kleinste Zahl innerhalb einer Liste von Ganzzahlen, die Verwendung von Rekursion, aber ich kann nicht für das Leben von mir erarbeiten einen Weg, es zu tun. Ich kann es tun, mit zu finden die kleinste Zahl mit dieser:

def smallest(int_list):

    if(len(int_list) == 1):
        return int_list[0]
    else:
        a = smallest(int_list[1:])
        b = int_list[0]

        if(a <= b):
            return a
        else:
            return b

Kann jemand mich in die richtige Richtung?

Erstellen Sie 2 Funktionen, eine, die findet die kleinsten und eine, die versucht zu finden, die nächste kleinste angesichts der Rückgabewert der ersten Funktion
Anstatt nur die kleinsten, versuchen, Rückgabe eines Tupels enthält die kleinste und zweitkleinste der Teil der Liste, die Sie bearbeitet habe, so weit. Halten Sie die Aktualisierung der Tupel bei jedem Schritt.
en.wikipedia.org/wiki/Quickselect beschreibt die Sache ziemlich gut.
überprüfen Sie meine Antwort, die ich umgesetzt so etwas wie @shridharama vorgeschlagen.
Eine Sache ist nicht sehr klar, Sie wollen zurück 2. kleinste auch Elemente, sind doppelte wie zurück 1 im [1,1,2,3]? Oder Sie wollen 2?

InformationsquelleAutor qND | 2015-01-26

Hier ist eine kurze Einführung, in dem nicht min() oder sorted(). Es funktioniert auch, wenn es doppelte Werte in der Liste.

def ss(e):
    if len(e)==2 and e[0]<=e[1]:return e[1]
    return ss(e[:-1]) if e[0]<=e[-1]>=e[1] else ss([e[-1]]+e[:-1])

print("The selected value was:", ss([5, 4, 3, 2, 1]))

InformationsquelleAutor Jason Sanchez

Hier:

def r_sort(a_list, ind):
    def rf(list_to_be_sorted, list_already_sorted):
        li = []
        if len(list_to_be_sorted) == 0:
            return list_already_sorted
        else:    
            x = min(list_to_be_sorted)    
            list_to_be_sorted.remove(x)
            li.append(x)
            return rf(list_to_be_sorted, list_already_sorted + li)
    return rf(a_list, [])[ind]

>>> r_sort([1,10,9,5,55,3,2], 1)  
2

InformationsquelleAutor

0

Sollte diese Arbeit. get_smallest_two_items() gibt ein Tupel mit dem kleinsten 2 Elemente aus dem 3 eingegeben. Umsetzung es sollte trivial sein. Beachten Sie auch, dass dieses setzt die minimale Länge der Liste ist 2.
```
def smallest(int_list):
   smallest_two = smallest_helper(int_list)
   return smallest_two[0] if smallest_two[0]<=smallest_two[1] else smallest_two[1]

def smallest_helper(int_list):

  if(len(int_list) == 2):
    return (int_list[0],int_list[1])
  else:
    a_b = smallest(int_list[1:])
    a = a_b[0]
    b = a_b[1]
    c = int_list[0]

    return get_smallest_two_items(a,b,c)
```
- Umm. Sinn kommentieren, bevor down-voting?
- sicher nicht, dass, wo get_smallest_two_items(a,b,c) kommen?
- du bist immer noch die Benennung der Funktion falsch...
- Wie genau? Es gibt die kleinste von a, b und c als Tupel wie bereits in meiner Antwort.
- haben Sie selbst getestet Codes? Sie haben keine, wo den Namen einer Funktion, die aufgerufen wird get_smallest_two_items()... es ist ein Fehler
- Ich habe bereits erwähnt in der Antwort, dass die Methode soll einfach zu implementieren ist. Mein Ziel war es, nicht zu schreiben, perfekt ausführbaren code, es war mehr zu Punkt OP in die richtige Richtung. Stackoverflow ist nicht dazu gedacht, für Löffel-Fütterung jede einzelne code-Zeile.
- ok, Sie haben einen gültigen Punkt, aber schwach, Sie sind mit sich gegenseitig rekursive Funktionen, die sich nicht wirklich viel erklären, noch keine klare Richtung. Ich werde abheben downvote, für einmal
InformationsquelleAutor shridharama

Einfacheres Beispiel als mein Kommentar:

def find_nth_smallest(n, int_list):
    smallest = min(int_list)
    if n <= 1:
        return smallest
    int_list = [v for v in int_list if v != smallest]
    if int_list:
        return max(find_nth_smallest(n - 1, int_list), smallest)
    return None

Beispiel:

Python 2.7.8 (default, Oct 20 2014, 15:05:19) 
[GCC 4.9.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from kthTerm import find_nth_smallest
>>> import random
>>> random.seed()
>>> int_list = [random.randint(1, 100) for _ in range(20)]
>>> int_list
[68, 50, 6, 36, 98, 15, 81, 36, 13, 71, 76, 77, 69, 75, 79, 53, 26, 25, 18, 62]
>>> find_nth_smallest(2, int_list)
13
>>> sorted(int_list)
[6, 13, 15, 18, 25, 26, 36, 36, 50, 53, 62, 68, 69, 71, 75, 76, 77, 79, 81, 98]

InformationsquelleAutor smac89

Hier ist ein Ansatz, der nicht Schlag den stack für große Listen. Es wäre besser zu verwalten die Suche Endpunkte manuell, anstatt schneiden die Einführung kopieren.

import random

def min2(xs):
    if len(xs) < 3: return xs
    n = len(xs) // 2
    return sorted(min2(xs[:n]) + [xs[n]] + min2(xs[n+1:]))[:2]

tk = range(100000)
random.shuffle(tk)
print min2(tk)

InformationsquelleAutor Paul Hankin

Hier ist eine rein rekursive Weise. Sie brauchen, um wieder das erste, kleinste und das zweitkleinste element in einem Tupel und so weiter.

def smallest(int_list):

    if(len(int_list) == 2):
        if (int_list[0] >= int_list[1]):
            return (int_list[0],int_list[1])
        else:
            return (int_list[1],int_list[0])
    else:
        first_smallest,second_smallest = smallest(int_list[1:])
        current_elem = int_list[0]
        if(second_smallest <= current_elem):
            return (second_smallest,current_elem)
        else:
            if (current_elem<=first_smallest):
               return (current_elem,first_smallest)
            else:
               return (first_smallest,second_smallest)



if __name__ == "__main__":    
    small = smallest([1,2,3,4])
    print small[1]
    //output 2

kleinste([2,1,3,4,5]) zurückgeben sollte, 2. Dies gibt (1, 3).

InformationsquelleAutor levi

-2

def second_smallest(my_list ein):

if len(my_list) == 2:
    return my_list[0] if my_list[0] > my_list[1] else my_list[1]

else:
    sec_least = second_smallest(my_list[1:])
    return sec_least if sec_least < my_list[0] else my_list[1]

second_smallest([2,1,3,4,5]) gibt 1 zurück, aber zurückkehren sollte, 2. second_smallest([1,1,2,3,4]) gibt 2 zurück, sollte aber 1 zurück.

InformationsquelleAutor jellyman2014

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.