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

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:

• 입력: 항목 = [[10,1000]], 쿼리 = [5]
• 출력: [0]
• 설명: 가격이 5 이하인 항목이 없으므로 항목을 선택할 수 없습니다.
  • 따라서 질의의 답은 0이 됩니다.

제약조건:

• 1 <= 항목.길이, 쿼리.길이 <= 10⁵
• 항목[i].length == 2
• 1 <= 가격_i, 뷰티_i, 쿼리[j] <= 10⁹

힌트:

1. 같은 항목을 반복해서 확인하지 않도록 스마트한 순서로 쿼리를 처리할 수 있나요?
2. 질의에 대한 답변을 다른 쿼리에 어떻게 사용할 수 있나요?

해결책:

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

접근하다

1. 가격순으로 품목 정렬:

   • 먼저 가격별로 항목을 정렬합니다. 이런 식으로 항목을 반복하면서 항목의 최대 아름다움을 주어진 가격까지 추적할 수 있습니다.

2. 원래 색인으로 쿼리 정렬:

   • 원래 인덱스와 쌍을 이루는 쿼리 배열을 만든 다음 쿼리 값을 기준으로 이 배열을 정렬합니다.
   • 정렬하면 가격이 오름차순으로 쿼리를 처리할 수 있고 가격이 낮은 경우 미용 가치를 반복적으로 다시 계산하는 것을 피할 수 있으므로 도움이 됩니다.

3. 항목과 쿼리를 동시에 반복:

   • 두 개의 포인터를 사용하여 각 쿼리를 처리합니다.
     • 각 쿼리에 대해 쿼리 가격보다 가격이 낮거나 같은 항목 위로 포인터를 이동합니다.
     • 이러한 항목을 살펴보며 최대 아름다움을 추적하고 이 값을 사용하여 현재 쿼리에 답하세요.
     • 이렇게 하면 여러 쿼리에 대해 항목을 반복적으로 확인하는 것을 방지할 수 있습니다.

4. 저장 및 반환 결과:

   • 처리가 완료되면 원본 인덱스를 기준으로 각 쿼리에 대한 최대 미용 결과를 저장하여 순서를 유지합니다.
   • 답변 배열을 반환합니다.

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

  
  
  설명:




항목 및 쿼리 정렬: 중복 계산 없이 효율적인 처리가 가능합니다.

2점 기법: 각 쿼리에 대해 한 번만 항목을 이동하여 과도한 계산을 방지합니다.

maxBeauty 추적: maxBeauty를 점진적으로 업데이트하여 각 쿼리가 지금까지 본 최고의 아름다움에 액세스할 수 있도록 합니다.



  
  
  복잡성




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

공간 복잡도: O(m) 결과를 ​​저장합니다.


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

연락처 링크

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

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


링크드인
깃허브



          

            
  

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