정렬된 양수 배열이 있다고 가정하고 이 배열은 오름차순으로 정렬되며 주어진 하위 집합의 요소 합계로 나타낼 수 없는 가장 작은 양수 값을 찾아야 합니다. 세트. O(n) 시간 안에 이 문제를 해결해야 합니다.
따라서 입력이 A =[1, 4, 8, 12, 13, 17]과 같으면 출력은 2가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=A의 크기
-
답 :=1
-
0에서 n 사이의 i에 대해 수행
-
A[i] <=대답이면
-
답변 :=답변 + A[i]
-
-
그렇지 않으면
-
루프에서 나오다
-
-
-
답변을 반환
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def get_smallest_element(A): n = len(A) answer = 1 for i in range (0, n ): if A[i] <= answer: answer = answer + A[i] else: break return answer A = [1, 4, 8, 12, 13, 17] print(get_smallest_element(A))
입력
[1, 4, 8, 12, 13, 17]
출력
2