선형 시간 복잡도의 목록에서 n번째로 큰 요소를 선택해야 하는 경우 두 가지 방법이 필요합니다. 가장 큰 요소를 찾는 방법과 목록을 두 부분으로 나누는 방법이 있습니다. 이 구분은 사용자가 부여한 'i' 값에 따라 다릅니다. 이 값을 기준으로 목록을 분할하여 가장 큰 요소를 결정합니다.
아래는 동일한 데모입니다 -
예시
def select_largest(my_list, beg, end, i):
if end - beg <= 1:
return my_list[beg]
pivot_val = start_partition(my_list, beg, end)
k = end - pivot_val
if i < k:
return select_largest(my_list, pivot_val + 1, end, i)
elif i > k:
return select_largest(my_list, beg, pivot_val, i - k)
return my_list[pivot_val]
def start_partition(my_list, beg, end):
pivot_val = my_list[beg]
i = beg + 1
j = end - 1
while True:
while (i <= j and my_list[i] <= pivot_val):
i = i + 1
while (i <= j and my_list[j] >= pivot_val):
j = j - 1
if i <= j:
my_list[i], my_list[j] = my_list[j], my_list[i]
else:
my_list[beg], my_list[j] = my_list[j], my_list[beg]
return j
my_list = input('Enter the list of numbers.. ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
i = int(input('Enter the value for i.. '))
ith_largest = select_largest(my_list, 0, len(my_list), i)
print('The result is {}.'.format(ith_largest)) 출력
Enter the list of numbers.. 34 67 12 0 999 Enter the value for i.. 1 The result is 999.
설명
-
list, 시작, 끝 및 'i' 값을 매개변수로 사용하는 'select_largest'라는 메서드가 정의되어 있습니다.
-
'i' 값에 따라 목록을 두 부분으로 나누는 'start_partition'이라는 또 다른 메서드가 정의되어 있습니다.
-
이 메소드는 'select_largest' 메소드에서 호출됩니다.
-
'select_largest'도 동일한 함수 내에서 다시 호출됩니다. 이것이 재귀가 작동하는 방식입니다.
-
숫자는 사용자의 입력으로 사용됩니다.
-
기본값에 따라 분할됩니다.
-
반복됩니다.
-
사용자로부터 'i' 값을 가져옵니다.
-
이 'i' 값을 기준으로 목록이 두 부분으로 나뉩니다.
-
목록 중 하나에서 'select_largest' 메소드가 호출됩니다.
-
출력은 콘솔에 표시됩니다.