배열의 순위 변환

1331. 배열의 순위 변환

난이도: 쉬움

주제: 배열, 해시 테이블, 정렬

정수 배열 arr이 주어지면 각 요소를 순위로 바꿉니다.

순위는 요소의 크기를 나타냅니다. 순위에는 다음과 같은 규칙이 있습니다.

• 순위는 1부터 시작하는 정수입니다.
• 요소가 클수록 순위가 높아집니다. 두 요소가 동일한 경우 해당 순위는 동일해야 합니다.
• 순위는 최대한 작아야 합니다.

예 1:

• 입력: arr = [40,10,20,30]
• 출력: [4,1,2,3]
• 설명: 40이 가장 큰 요소입니다. 10이 가장 작습니다. 20은 두 번째로 작은 숫자입니다. 30은 세 번째로 작은 숫자입니다.

예 2:

• 입력: arr = [100,100,100]
• 출력: [1,1,1]
• 설명: 동일한 요소는 동일한 순위를 공유합니다.

예 3:

• 입력: arr = [37,12,28,9,100,56,80,5,12]
• 출력: [5,3,4,2,8,6,7,1,3]

제약조건:

• 0 <= arr.length <= 10⁵
• -10⁹ <= arr[i] <= 10⁹

힌트:

1. 임시 배열을 사용하여 배열을 복사하고 정렬합니다.
2. 각 요소의 순위는 정렬된 배열에서 해당 요소보다 작은 고유 요소 수에 1을 더한 값입니다.

해결책:

다음 단계로 나눌 수 있습니다.

1. 배열 복사 및 정렬: 이는 각 고유 요소의 순위를 결정하는 데 도움이 됩니다.
2. 해시 맵을 사용하여 요소에 순위 할당: 여러 요소가 동일한 값을 공유할 수 있으므로 해시 맵(PHP의 연관 배열)은 각 요소를 해당 순위에 매핑하는 데 도움이 됩니다.
3. 원래 요소를 해당 순위로 바꾸기: 해시 맵을 사용하면 원래 배열의 각 요소를 해당 순위로 바꿀 수 있습니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1331. 배열의 순위 변환

<?php
/**
 * @param Integer[] $arr
 * @return Integer[]
 */
function arrayRankTransform($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$arr1 = [40, 10, 20, 30];
print_r(arrayRankTransform($arr1)); // Output: [4, 1, 2, 3]

$arr2 = [100, 100, 100];
print_r(arrayRankTransform($arr2)); // Output: [1, 1, 1]

$arr3 = [37, 12, 28, 9, 100, 56, 80, 5, 12];
print_r(arrayRankTransform($arr3)); // Output: [5, 3, 4, 2, 8, 6, 7, 1, 3]
?>





  
  
  설명:




배열 복사 및 정렬:


$sorted 입력 배열의 복사본을 만들고 정렬합니다. 이는 각 고유 요소의 순위를 결정하는 데 도움이 됩니다.



요소에 순위 지정:


정렬된 배열을 반복하고 해시 맵 $rank를 사용하여 각 고유 요소의 순위를 저장합니다.
isset을 사용하여 요소에 이미 순위가 지정되었는지 확인합니다. 그렇지 않은 경우 현재 순위를 할당하고 순위를 높입니다.



요소를 순위로 바꾸기:


그런 다음 원본 배열을 반복하고 $rank 해시 맵에서 각 요소를 찾아 해당 순위로 바꿉니다.





  
  
  시간 복잡도:



배열을 정렬하려면 O(n log n)이 필요합니다. 여기서 n은 배열의 크기입니다.
순위를 지정하고 값을 바꾸려면 O(n)이 필요합니다.
전체 시간 복잡도는 O(n log n)입니다.


이 솔루션은 단순성을 유지하면서 대규모 어레이를 효율적으로 처리합니다.

연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 배열의 순위 변환의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!