주어진 연산으로 배열을 최대 하나의 요소로 줄입니다.

이 문제에서는 매 라운드마다 주어진 연산을 수행하여 배열 크기를 1 또는 0으로 줄입니다.

각 라운드에서 배열을 정렬하여 각 반복에서 최대 요소를 얻을 수 있습니다. 또한 헤드 데이터 구조를 사용하여 코드 성능을 향상시킬 수도 있습니다.

문제 설명 - 숫자[] 배열이 제공됩니다. 다음을 수행하여 배열을 줄여야 합니다.

• 배열에서 가장 큰 요소 두 개를 선택하세요.

• 두 요소가 동일한 경우 배열에서 두 요소를 삭제하세요.

• 두 요소가 동일하지 않으면 배열에서 두 요소를 삭제하고 배열에 abs(first − second)를 삽입하세요.

배열의 마지막 요소를 인쇄하세요. 배열이 비어 있으면 0을 인쇄합니다.

예

들어가세요

으아악

출력

으아악

지침

• 첫 번째 라운드에서는 9와 8을 가져와 그 차이를 배열에 추가합니다. 따라서 배열은 [5, 3, 2, 5, 1]이 됩니다.

• 두 번째 라운드에서는 5와 5를 선택합니다. 따라서 배열은 [3, 2, 1]이 됩니다.

• 다음 라운드에서는 3과 2를 가져갑니다. 따라서 배열은 [1, 1]

이 됩니다.

• 마지막 라운드에서는 1과 1을 가져갑니다. 따라서 배열은 비어 있고 0을 인쇄합니다.

들어가세요

으아악

출력

으아악

설명- 5 쌍을 두 번 삭제하고 5 하나가 배열에 남습니다.

들어가세요

으아악

출력

으아악

설명 - 먼저 8과 7을 선택합니다. 따라서 배열은 [4, 1, 6]이 됩니다. 그 다음에는 4와 6을 선택합니다. 따라서 배열은 [1, 2]가 됩니다. 마지막 작업에서 배열은 [1]이 됩니다.

방법 1

이 방법에서는 배열의 크기가 1 또는 0이 될 때까지 배열을 반복합니다. 각 반복에서 배열을 정렬하고 정렬된 배열의 처음 2개 요소에 대해 지정된 작업을 수행합니다. 마지막으로 배열 크기에 따라 출력을 인쇄합니다.

알고리즘

1단계 - 배열의 크기를 "len" 변수에 저장합니다.

2단계 - while 루프를 사용하여 배열 탐색을 시작합니다.

3단계 - 루프에서 sort() 메서드를 사용하여 배열을 역정렬합니다.

4단계 - 배열의 첫 번째 요소와 두 번째 요소를 가져옵니다. 또한 배열의 첫 번째 요소와 두 번째 요소 간의 차이를 계산합니다.

5단계− 차이가 0이면 배열의 처음 두 요소를 삭제하고 'len'을 2로 줄입니다. 차이가 0이 아니면 처음 2개 요소를 삭제하고 'len'에서 1을 뺀 값을 줄입니다.

6단계 - 마지막으로 배열의 크기가 0이면 0을 반환합니다. 그렇지 않으면 배열의 첫 번째 요소가 반환됩니다.

예

으아악

출력

으아악

시간 복잡도 - O(N*NlogN), 여기서 O(N)은 배열을 반복하는 데 사용되고 O(NlogN)은 각 반복에서 배열을 정렬하는 데 사용됩니다.

공간 복잡성 - 배열을 정렬하는 O(N)입니다.

방법 2

이 방법에서는 힙 데이터 구조를 구현하는 우선 순위 큐를 사용합니다. 항상 정렬된 순서로 요소를 저장합니다. 따라서 처음 2개의 가장 큰 요소를 쉽게 제거할 수 있습니다.

알고리즘

1단계 - 우선순위 대기열이라는 "p_queue"를 정의합니다.

2단계 - 모든 배열 요소를 우선순위 대기열에 삽입합니다.

3단계 - 우선순위 대기열 크기가 1보다 커질 때까지 반복합니다.

4단계- 우선순위 큐의 처음 2개 요소를 하나씩 삭제합니다.

5단계 - 두 요소의 차이점을 찾아보세요.

6단계 - 차이가 0이 아니면 우선순위 큐로 푸시합니다.

7단계− 마지막으로 대기열 크기가 0이면 0을 반환합니다.

8단계- 그렇지 않으면 대기열 맨 위에 있는 요소를 반환합니다.

예

으아악

출력

으아악

시간 복잡도 - 우선순위 큐에 요소를 삽입하고 삭제하는 시간 복잡도는 O(NlogN)입니다.

공간 복잡성 - O(N)은 우선순위 대기열에 요소를 저장합니다.

우선순위 큐 데이터 구조는 요소를 삽입하거나 삭제한 후 배열 데이터를 특정 순서로 정렬해야 할 때 항상 유용합니다. 힙 데이터 구조를 구현하여 삽입 및 삭제가 가능합니다.

위 내용은 주어진 연산으로 배열을 최대 하나의 요소로 줄입니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!