집 > 기사 > 백엔드 개발 > 각 검색어에 대한 가장 아름다운 항목

각 검색어에 대한 가장 아름다운 항목

Most Beautiful Item for Each Query

2070. 검색어별 가장 아름다운 아이템

난이도:중

주제: 배열, 이진 검색, 정렬

items[i] = [price_i, beauty_i]가 price 및 beauty를 나타내는 2D 정수 배열 항목이 제공됩니다. 항목별로

0-인덱스 정수 배열 쿼리도 제공됩니다. 각 검색어[j]에 대해 가격이 검색어[j]와 이하인 항목의 최대 아름다움을 확인하려고 합니다. 해당 항목이 존재하지 않는 경우 이 쿼리에 대한 답변은 0입니다.

답변답변[j]이 j번째 쿼리에 대한 답인 쿼리와 동일한 길이의 답변 배열을 반환합니다.

예 1:

입력: 항목 = [[1,2],[3,2],[2,4],[5,6],[3,5]], 쿼리 = [1,2,3 ,4,5,6]
출력: [2,4,5,5,6,6]
설명:
- 쿼리[0]=1의 경우 [1,2]는 가격
- 쿼리[1]=2의 경우 고려할 수 있는 항목은 [1,2] 및 [2,4]입니다.
- 그 중 최대 미모는 4입니다.
- 쿼리[2]=3 및 쿼리[3]=4의 경우 고려할 수 있는 항목은 [1,2], [3,2], [2,4] 및 [3,5]입니다.
- 그 중 최대 미모는 5입니다.
- 쿼리[4]=5 및 쿼리[5]=6의 경우 모든 항목을 고려할 수 있습니다.
- 그러므로 그에 대한 답은 모든 아이템의 최대 아름다움, 즉 6입니다.

예 2:

입력: 항목 = [[1,2],[1,2],[1,3],[1,4]], 쿼리 = [1]
출력: [4]
설명: 모든 품목의 가격은 1이므로 아름다움이 최대 4인 품목을 선택합니다.
- 여러 품목의 가격 및/또는 디자인이 동일할 수 있습니다.

예 3:

제약조건:

힌트:

해결책:

정렬 및 이진 검색 기술을 사용할 수 있습니다. 계획은 다음과 같습니다.

가격순으로 품목 정렬:
- 먼저 가격별로 항목을 정렬합니다. 이런 식으로 항목을 반복하면서 항목의 최대 아름다움을 주어진 가격까지 추적할 수 있습니다.
원래 색인으로 쿼리 정렬:
- 원래 인덱스와 쌍을 이루는 쿼리 배열을 만든 다음 쿼리 값을 기준으로 이 배열을 정렬합니다.
- 정렬하면 가격이 오름차순으로 쿼리를 처리할 수 있고 가격이 낮은 경우 미용 가치를 반복적으로 다시 계산하는 것을 피할 수 있으므로 도움이 됩니다.
항목과 쿼리를 동시에 반복:
- 두 개의 포인터를 사용하여 각 쿼리를 처리합니다.
  - 각 쿼리에 대해 쿼리 가격보다 가격이 낮거나 같은 항목 위로 포인터를 이동합니다.
  - 이러한 항목을 살펴보며 최대 아름다움을 추적하고 이 값을 사용하여 현재 쿼리에 답하세요.
  - 이렇게 하면 여러 쿼리에 대해 항목을 반복적으로 확인하는 것을 방지할 수 있습니다.
저장 및 반환 결과:
- 처리가 완료되면 원본 인덱스를 기준으로 각 쿼리에 대한 최대 미용 결과를 저장하여 순서를 유지합니다.
- 답변 배열을 반환합니다.

이 솔루션을 PHP: 2070으로 구현해 보겠습니다. 검색어별 가장 아름다운 아이템

항목 및 쿼리 정렬: 중복 계산 없이 효율적인 처리가 가능합니다.
2점 기법: 각 쿼리에 대해 한 번만 항목을 이동하여 과도한 계산을 방지합니다.
maxBeauty 추적: maxBeauty를 점진적으로 업데이트하여 각 쿼리가 지금까지 본 최고의 아름다움에 액세스할 수 있도록 합니다.

시간 복잡도: 항목 및 쿼리 정렬의 경우 O(n log n m log m), O(n m) 처리용, 여기서 n은 항목의 길이이고 m은 쿼리의 길이입니다.
공간 복잡도: O(m) 결과를 저장합니다.

이 솔루션은 효율적이며 문제의 제약 조건을 충족합니다.

연락처 링크

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

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

위 내용은 각 검색어에 대한 가장 아름다운 항목의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명：