數組的秩變換

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 5
• -10⁹ 9

提示：

1. 使用臨時數組複製數組並排序。
2. 每個元素的排名是排序數組中小於它的唯一元素的數量加一。

解：

我們可以將其分解為以下步驟：

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]
?>

解釋：

1. 複製陣列並排序：

   • 我們建立輸入陣列 $sorted 的副本並對其進行排序。這有助於確定每個獨特元素的排名。

2. 為元素分配排名：

   • 我們迭代排序後的陣列並使用雜湊映射 $rank 來儲存每個唯一元素的排名。
   • 我們使用 isset 來檢查元素是否已經被分配了排名。如果沒有，我們分配當前排名並遞增它。

3. 用元素的等級取代元素：

   • 然後，我們迭代原始數組，並透過在 $rank 雜湊映射中找到每個元素，將其替換為其對應的排名。

時間複雜度：

• 對陣列進行排序需要 O(n log n)，其中 n 是陣列的大小。
• 分配排名和替換值需要O(n)。
• 整體時間複雜度為O(n log n)。

此解決方案可有效處理大型數組，同時保持簡單性。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是數組的秩變換的詳細內容。更多資訊請關注PHP中文網其他相關文章！