배열에서 두 번째로 큰 요소를 찾는 C++ 프로그램

배열의 목적은 기본 주소와 인덱스를 사용하여 액세스할 수 있는 일련의 메모리 위치에 유사한 유형의 데이터를 저장하는 것입니다. 우리는 다양한 목적으로 데이터를 보관하기 위해 다양한 애플리케이션에서 배열을 사용합니다. 가장 작은 요소와 가장 큰 요소를 찾는 것은 정렬 등을 포함한 여러 응용 프로그램에 필요한 배열의 매우 일반적인 예입니다. 이번 글에서는 C++ 배열에서 두 번째로 큰 요소를 찾는 방법을 배워보겠습니다.

예제를 통해 개념 이해하기

으아악

위의 예에는 배열에 12개의 요소가 있습니다. 배열에서 가장 큰 요소는 99이고, 두 번째로 큰 요소는 89입니다. 첫 번째 방법에서는 두 번째로 큰 요소를 찾으려면 요소를 오름차순 또는 내림차순으로 정렬한 다음 두 번째에서 마지막 또는 두 번째 요소로 직접 반환하여 두 번째로 큰 요소를 얻으면 됩니다. 알고리즘은 다음과 같습니다 -

알고리즘

• n 크기의 배열 A를 가져옵니다

• 값이 증가하지 않는 순서로 배열 A를 정렬합니다

• returns A[ 1 ] // 0번째 인덱스에 가장 큰 요소가 포함되어 있기 때문입니다

예

으아악

출력

으아악

이중 순회 사용

위의 방법은 간단해 보이지만 이 문제에는 프로세스가 효율적이지 않습니다. 정렬을 사용하고 있으므로 정렬을 수행하는 데는 최소한 O(n.log n) 시간이 걸립니다. 하지만 이 문제를 선형 시간 내에 해결할 수도 있습니다. 현재 방법에서는 요소 배열을 두 번 반복하고 두 번째로 큰 요소를 찾습니다. 알고리즘을 확인해 보겠습니다.

알고리즘

• n 크기의 배열 A를 가져옵니다

• 최대 := -무한

• 최대 초 := -무한대

• A의 각 요소 e에 대해

  를 실행합니다.

  • e가 최대값보다 크면

    • max = e

  • 종료

• 끝

• A의 각 요소 e에 대해

  를 실행합니다.

  • e가 secLargest보다 크고 maximum보다 작은 경우

    • 최대 초 = e

  • 종료

• 끝

• 최대 초 반환

예

으아악

출력

으아악

단일 순회 사용

위 솔루션은 배열을 두 번 반복합니다. 첫 번째 실행에서는 배열에서 가장 큰 요소를 찾은 다음 두 번째 실행에서는 첫 번째 가장 큰 요소보다 크지 않은 가장 큰 요소를 검색합니다. 배열은 선형 데이터 구조이므로 각 순회에는 O(n) 시간이 걸리므로 최종 솔루션 시간은 O(2n)이며 O(n)과 유사하게 선형이기도 합니다. 하지만 이는 효율적인 솔루션이 아니며, 한 번만 통과하면 이 문제를 해결할 수 있습니다. 알고리즘을 살펴보겠습니다.

알고리즘

• n 크기의 배열 A를 가져옵니다

• 최대 := A[0]

• 1부터 n - 1까지의 시작 인덱스를 얻으려면 다음을 수행하세요.

  • 현재 요소 A[i]가 최대값보다 큰 경우

    • 초 최대 := 최대

    • 최대 := A[ i ]

  • 그렇지 않고 A[ i ]가 maximum과 secLargest 사이에 있으면

    • 최대 초 := A[ i ]

  • 종료

• 끝

• 최대 초 반환

예

으아악

출력

으아악

결론

이 글에서는 주어진 배열에서 두 번째로 큰 요소를 찾는 세 가지 방법을 배웠습니다. 첫 번째 방법은 정렬을 사용하는 것입니다. 그러나 이 솔루션은 효율적이지 않으며 최소한 O(n log n ) 시간이 걸립니다. 후자의 솔루션은 선형 시간이 필요하기 때문에 매우 효율적입니다. 두 번째 솔루션은 어레이에 대해 이중 패스를 사용하는 것입니다. 이는 세 번째 솔루션에 표시된 것처럼 단일 패스로 최적화할 수도 있습니다.

위 내용은 배열에서 두 번째로 큰 요소를 찾는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!