数组的秩变换

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中文网其他相关文章！