>백엔드 개발 >PHP 튜토리얼 >모든 요소를 ​​표시한 후 배열의 점수 찾기

모든 요소를 ​​표시한 후 배열의 점수 찾기

Patricia Arquette
Patricia Arquette원래의
2024-12-15 13:36:24679검색

Find Score of an Array After Marking All Elements

2593. 모든 요소를 ​​표시한 후 배열의 점수 찾기

난이도:

주제: 힙(우선순위 큐), 정렬, 배열, 시뮬레이션, 해시 테이블, Ordered Set, Ordered Map, Greedy, Monotonic Stack, 슬라이딩 윈도우, 두 포인터, 스택, 큐, 비트 조작, 분할 정복, 동적 프로그래밍, 이중 연결 목록, 데이터 스트림, 기수 정렬, 역추적, 비트마스크, 트리, 디자인, 해시 함수, 문자열, 반복자, 계산 정렬, 연결 목록

양의 정수로 구성된 배열 num이 제공됩니다.

점수 = 0부터 시작하여 다음 알고리즘을 적용합니다.

  • 표시되지 않은 배열 중 가장 작은 정수를 선택하세요. 동점인 경우 지수가 가장 작은 것을 선택하세요.
  • 선택한 정수 값을 점수에 추가하세요.
  • 선택한 요소와 인접한 두 요소(존재하는 경우)를 표시합니다.
  • 모든 배열 요소가 표시될 때까지 반복합니다.

위 알고리즘을 적용하여 얻은 점수를 반환합니다.

예 1:

  • 입력: 숫자 = [2,1,3,4,5,2]
  • 출력: 7
  • 설명: 요소를 다음과 같이 표시합니다.
    • 1은 표시되지 않은 가장 작은 요소이므로 이 요소와 인접한 두 요소인 [2,1,3,4,5,2]로 표시합니다.
    • 2는 표시되지 않은 가장 작은 요소이므로 이 요소와 왼쪽 인접 요소인 [2,1,3,4,5,2]로 표시합니다.
    • 4는 표시되지 않은 유일한 요소이므로 [2,1,3,4,5,2]로 표시합니다.
    • 저희 점수는 1 2 4 = 7입니다.

예 2:

  • 입력: 숫자 = [2,3,5,1,3,2]
  • 출력: 5
  • 설명: 요소를 다음과 같이 표시합니다.
    • 1은 표시되지 않은 가장 작은 요소이므로 이 요소와 인접한 두 요소인 [2,3,5,1,3,2]로 표시합니다.
    • 2는 표시되지 않은 가장 작은 요소입니다. 두 개가 있으므로 가장 왼쪽에 있는 것을 선택하여 인덱스 0에 있는 것을 표시하고 오른쪽에 인접한 요소인 [2,3,5,1,3, 2].
    • 2는 표시되지 않은 유일한 요소이므로 [2,3,5,1,3,2]로 표시합니다.
    • 저희 점수는 1 2 2 = 5입니다.

제약조건:

  • 1 <= nums.length <= 105
  • 1 <= 숫자[i] <= 106

힌트:

  1. 요소와 인접 요소를 표시하는 과정을 시뮬레이션해 보세요.
  2. 이미 표시된 요소가 있으면 건너뛰세요.

해결책:

정렬된 배열이나 우선순위 큐를 사용하여 표시되지 않은 가장 작은 요소를 추적함으로써 표시 프로세스를 효율적으로 시뮬레이션할 수 있습니다. 따라서 다음 접근 방식을 사용할 수 있습니다.

계획:

  1. 입력 구문 분석: 배열 번호를 읽고 점수 및 채점 상태에 대한 변수를 초기화합니다.
  2. 힙(우선순위 대기열):
    • 최소 힙을 사용하여 각 단계에서 표시되지 않은 가장 작은 요소를 효율적으로 추출합니다.
    • 각 요소를 인덱스(값, 인덱스)와 함께 힙에 삽입하여 가장 작은 인덱스를 기준으로 연결을 관리합니다.
  3. 마킹 요소:
    • 표시된 배열을 유지하여 요소와 인접한 요소가 표시되었는지 추적합니다.
    • 힙의 요소를 처리할 때 이미 표시된 요소는 건너뜁니다.
    • 현재 요소와 두 개의 인접 요소(존재하는 경우)를 표시합니다.
    • 현재 요소의 값을 점수에 추가합니다.
  4. 반복: 모든 요소가 표시될 때까지 계속합니다.
  5. 출력: 누적 점수를 반환합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 2593. 모든 요소를 ​​표시한 후 배열의 점수 찾기






설명:

  1. 힙 구성:

    • usort 함수는 값을 기준으로 배열을 정렬하고 값이 묶인 경우 인덱스를 기준으로 정렬합니다.
    • 이렇게 하면 항상 가장 작은 인덱스로 표시되지 않은 가장 작은 요소를 처리할 수 있습니다.
  2. 마킹 로직:

    • 표시되지 않은 각 요소에 대해 표시된 배열을 사용하여 해당 요소와 인접 요소를 표시합니다.
    • 이렇게 하면 이전에 표시된 요소를 효율적으로 건너뛸 수 있습니다.
  3. 시간 복잡성:

    • 힙 정렬: O(n log n)
    • 힙 처리: O(n)
    • 전체: O(n log n), 이는 주어진 제약 조건에 효율적입니다.
  4. 공간 복잡성:

    • 표시된 배열: O(n)
    • 힙: O(n)
    • 합계: O(n)

이 솔루션은 제약 조건을 충족하며 대규모 입력에 효율적으로 작동합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

  • 링크드인
  • 깃허브

위 내용은 모든 요소를 ​​표시한 후 배열의 점수 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.