dselectO (n) 시간에 정렬되지 않은 정수 (중복 없음)의 주어진 목록에서 i 번째 순서 통계를 찾아 퀵 정렬 원칙에 편승합니다. i 번째 순서 통계는 주어진 목록의 정렬 된 버전에서 i 번째로 작은 요소로 정의됩니다. 따라서 1 차 통계는 가장 작은 요소가되고 n 차 통계는 가장 큰 요소가됩니다.
실행에, 나는 수 IndexError: list index out of range에 return arr[l]의 말에 dselect기능. 나는 오류가 나 하드 코딩으로 인해 발생 생각 l으로 0목록에있는 재귀 호출에 medians온 dselect기능. (4 행)
이 오류를 방지하려면 어떻게해야합니까? l재귀 호출 에의 값을 어떻게 입력해야 합니까? 이것이이 오류의 원인일까요? 이것이 어리석은 질문이라면 자유롭게 지적하고이 질문을 삭제하겠습니다. 나는 이것에 대해 꽤 오랫동안 붙어 있기 때문에 이것을 물어야 만했습니다. 감사.
def dselect(arr, l, r, i):
if l < r:
#finding pivot deterministically
medians = createMedianList(arr, l, r)
pivot = dselect(medians, 0, len(medians) - 1, len(medians) // 2) #line4
pivot = partition(arr, l, r, pivot)
if pivot + 1 == i:
return arr[pivot]
elif pivot + 1 > i:
return dselect(arr, l, pivot - 1, i)
else:
return dselect(arr, pivot + 1, r, i)
return arr[l]
def partition(arr, l, r, pivot):
pivotIndex, i = arr.index(pivot), l
arr[l], arr[pivotIndex] = arr[pivotIndex], arr[l]
for j in range(l + 1, r + 1):
if arr[j] < arr[l]:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[l], arr[i] = arr[i], arr[l]
return i
def createMedianList(arr, l, r):
medians = []
for i in range(l, (r + 1) - 5 + 1):
temp = sorted(arr[i:i + min(5, (r - l + 1) - i)])
medians.append(temp[len(temp) // 2])
return medians
if __name__ == '__main__':
arr = [5, 2, 4, 3, 1, -1]
#arr = list(map(int, open('select.txt').read().splitlines()))
print(dselect(arr, 0, len(arr) - 1, int(input('Which order
statistic to find? '))))
문제는 createMedianList때때로 빈 목록을 반환한다는 l >= r-3것입니다. 이것은 결국 발생할 경우 발생합니다. createMedianList빈 목록을 반환하지 않도록 에 무언가를 추가하는 것이 좋습니다 . 예 : if medians==[]:medians=[arr[0]]또는 유사한 것 (중위수에 대해 원하는 속성에 따라 다름).
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다