C++ 中数组中每个元素的超越计数器

算法问题解决中的一个基本问题是超越计数（surpasser count），它衡量数组元素之间的相对顺序。它计算数组中每个元素右侧严格大于该元素的元素数量。当我们需要分析数据集中元素的相对重要性时，尤其是在数据分析、排名系统、竞争性编程等领域，它非常有价值。

其次，计算超越计数问题既具有教育意义又具有实践意义。在教育方面，它教授或更确切地说，向学生和程序员介绍了数组遍历、比较和数据结构以提高计算效率。它可以实际应用于各种领域，从股票价格分析到通过计算在给定股票之后表现更好的股票数量来识别未来趋势。

对于大型数据集，存在一个朴素的 O(n^2) 解决方案，其中每个元素都与数组中所有后续元素进行比较，但这非常耗时。因此，可以通过高级技术来解决这种低效率，例如分治法和 Fenwick 树（二叉索引树）。为了将此解决方案扩展到更大的数组，我们优化了这些技术的计算，使其运行时间为 O(nlogn)。

学习和解决超越计数问题是扩展我们对算法和数据结构理解的机会，并且应该是一个明智选择有助于高效计算的工具的场合。这个问题是可以通过巧妙的技术和周到的设计来优化复杂性的一个绝佳示例。

方法 1：暴力方法

计算超越计数的朴素方法是最简单、最直接的方法。这种方法定义了有多少元素大于它右侧的所有元素。它使用两个嵌套循环，外层循环固定在一个元素上，内层循环遍历剩余元素来计算更大的元素。

这种方法的时间复杂度将是 O(n^2)，因为外层循环需要 n 次迭代，而内层循环对于每个元素最多需要 n-1 次迭代。它易于理解和实现，但由于其 O(n^2) 的运行时间，它只能用于小型数据集。假设我们才刚刚开始接触基本问题。在这种情况下，朴素法是一种理想的方法，如果我们采用分治法或 Fenwick 树等更优化的方法，朴素法不适用于性能关键型应用程序。

示例

让我们通过一个例子来说明使用朴素方法在 C++ 中计算数组中每个元素的超越计数。

输出

Surpasser Count Calculator
This program calculates the surpasser count
for each element in an array using the brute
force approach.
---------------------------------------------
Enter the number of elements in the array: 5
Enter the elements of the array:
Element 1: 23
Element 2: 45
Element 3: 42
Element 4: 67
Element 5: 59
Input array successfully read!
Input Array:  23  45  42  67  59 
Now calculating surpasser counts...
Calculating surpasser counts step-by-step:
Element at index 0 (23):
  Comparing 23 with 45... Surpasser found!
  Comparing 23 with 42... Surpasser found!
  Comparing 23 with 67... Surpasser found!
  Comparing 23 with 59... Surpasser found!
  Total surpassers for 23: 4
Element at index 1 (45):
  Comparing 45 with 42... Not a surpasser.
  Comparing 45 with 67... Surpasser found!
  Comparing 45 with 59... Surpasser found!
  Total surpassers for 45: 2
Element at index 2 (42):
  Comparing 42 with 67... Surpasser found!
  Comparing 42 with 59... Surpasser found!
  Total surpassers for 42: 2
Element at index 3 (67):
  Comparing 67 with 59... Not a surpasser.
  Total surpassers for 67: 0
Element at index 4 (59):
  Total surpassers for 59: 0
Surpasser counts calculated successfully!
Final Results:
     Index   Element    Surpasser Count
----------------------------------------
         0        23                   4
         1        45                   2
         2        42                   2
         3        67                   0
         4        59                   0
Thank you for using the Surpasser Count Calculator!   

说明

1. displayArray 函数
   • 它是一个函数，以数组为参数，用于打印数组的内容。它接受两个参数：数组和一个标签。
   • 此库用于选择 setw 函数，以确保其整齐地显示并保持数组元素之间的一致性。
2. calculateSurpasserCounts 函数
   • 它计算每个元素的超越计数。它通过使用两个嵌套循环来实现：在外层循环（i 循环）中，我们遍历数组中的每个项，并将每个项视为要检查的当前项。内层循环（j 循环）将当前元素与它之后的所有其他元素（即索引更高的元素）进行比较。
   • 当内层循环中的元素 (arr[j]) 大于外层循环中的元素 (arr[i]，即第二个下标中的数组元素大于第一个子数组中的相应元素) 时，它会计算 arr[j] 的超越者。
   • 在每一步，它都会打印有关比较的详细信息。
3. inputArray 函数
   • 此函数接受用户输入的数组大小 (n) 和元素本身。它用用户输入填充数组并返回该数组。
4. displayResults 函数
   • 最后，此函数查找超越计数并对其进行格式化，以表格形式显示最终结果。它映射元素、其索引以及其相邻元素的超越数量。
5. main 函数
   • main() 函数控制程序的流程。首先，它调用 inputArray 函数从用户那里获取输入。之后，它调用 displayArray 函数显示传入的数组。最后，它调用 calculateSurpasserCounts 函数来计算超越计数。
   • 在这里，它报告显示结果以打印出超越每个元素的样本数量的结果。
6. 流程和输出
   • 程序的第一个消息是介绍性消息。它询问用户输入一个数组，然后通过朴素法计算超越计数，最后将其打印成格式良好的视图。打印语句详细说明了每个元素如何被确定具有超越计数。

复杂度分析

时间复杂度

可以通过检查用于计算每个元素的超越计数的循环来分析代码中采用的朴素方法。

• 外层循环：外层循环遍历数组中的每个元素一次。在此循环中，如果有 n 个元素，则数组将运行 n 次。
• 内层循环：在外层循环中，内层循环将每个元素与它后面的每个元素进行比较。每个元素 i 的内层循环有 n-i-1 次迭代。当 i 为 0 时，内层循环的运行次数最多，此时为 n-1。随着 i 的增加，内层循环的迭代次数会减少。

因此，朴素法的复杂度为 O(n²)。对于每个元素，它是二次方的，因为我们对数组中它后面的所有元素进行线性次数的比较。

空间复杂度

除了输入数组，额外使用的空间决定了程序的空间复杂度。

• 输入数组：额外空间复杂度不包括输入数组（它已经是输入的一部分）。
• 超越计数数组：我们创建了一个 surpasserCount 数组来存储每个元素的超越计数。因此，此数组的大小与输入数组相同，占用 O(n) 空间。
• 辅助变量：使用几个整数变量（循环计数器、数组索引等）只需要常量空间 (O(1))。

因此，用于存储 surpasserCount 数组的空间复杂度由 O(n) 决定。

方法二：Fenwick 树方法

Fenwick 树（也称为二叉索引树）是一种用于对累积频率表执行操作的数据结构。它允许 O(log n) 时间的更新和查询操作。在超越计数问题（我们想计算每个元素右侧有多少元素大于它）中，Fenwick 树用于在从右向左遍历数组时有效地跟踪元素。

通过使用坐标压缩技术，我们将数组元素拟合到与 Fenwick 树使用的 1 基索引兼容的空间中。对于每个元素，我们查询树以了解迄今为止遇到了多少个较大的元素，然后将当前元素添加到树中。这给了我们一个 O(n log n) 的时间复杂度解决方案，运行速度比朴素解决方案快得多。

示例

让我们通过一个例子来说明使用 Fenwick 树方法在 C++ 中计算数组中每个元素的超越计数。

输出

Enter the number of elements in the array: 5
Enter the elements of the array: 
Element 1: 34
Element 2: 45
Element 3: 56
Element 4: 67
Element 5: 78
Input Array: 34 45 56 67 78 
Final Results:
Element | Surpasser Count
-------------------------
34      | 4
45      | 3
56      | 2
67      | 1
78      | 0
End of Program   

说明

1. Fenwick 树（二叉索引树）类

FenwickTree 类是解决方案的核心，它提供了两个基本操作：

• update(index, value)：此方法更新 Fenwick 树中指定索引处的值（增加/减少），并将该值添加到当前的 Fenwick 树中。如果是更新，它会通过树结构传播，确保树将维护其元素的累积频率。
• query(index)：此方法用于累积（求和）树中从索引 1 到给定索引的所有元素的频率。有趣的是，它有效地查询小于或等于某个值的元素的数量。

由于其结构，Fenwick 树非常适合需要快速累积和查询的此类问题，其更新和查询时间均为 O(log n)。

2. 坐标压缩

• 如果输入数组值可能很大或稀疏，则需要进行坐标压缩。但是，我们需要将 Fenwick 树映射到一个更小的连续范围，因此我们将数组的值映射到一个更小的范围。这使我们能够避免使用大型稀疏 Fenwick 树。
• coordinateCompress 函数合并重复值，对去除重复值后的数组进行排序，并将现有元素压缩到每个唯一元素到 1 基索引。这使我们能够有效地在 Fenwick 树中使用这些压缩索引。

3. 计算超越者

countSurpassers 函数计算 数组 中每个元素的超越者数量。

• 从右向左遍历：函数从右向左遍历数组。它为每个元素查询 Fenwick 树，以确定它比多少个元素大，即超越了多少个元素。
• 更新 Fenwick 树：接下来，函数计算当前元素的超越计数，然后使用当前元素的压缩索引更新 Fenwick 树，以便将来查询使用。

通过这种方法，我们每个元素只检查一次，并且每个元素的结果计算时间为 O(log n)。因此，整个运行时间为 O(n log n)。

4. Main 函数和用户交互

• 用户输入：主函数根据数组的大小和每个元素读取。之后，它调用 countSurpassers 函数来计算超越计数的值。
• 显示结果：计算数组中每个元素及其对应的超越计数，然后以表格形式显示结果。

复杂度分析

时间复杂度

坐标压缩

对数组中的元素进行排序需要 O(n log n) 时间。可以通过遍历数组并将每个元素的压缩索引放入映射（map）中来在 O(n) 时间内完成。由于排序步骤，坐标压缩的总时间为 O(n log n)。

Fenwick 树操作

对于数组中的每个元素，我们执行两个主要操作：

• 查询：通过查询 Fenwick 树确定超越者（大于当前元素的元素）的数量。Fenwick 树在其查询操作中支持 O(log n) 时间。
• 更新：之后，我们查询并使用当前元素的计数更新 Fenwick 树。更新操作也需要 O(log n) 时间。

这两个操作（查询和更新）每个元素都需要 O(log n) 时间，但由于我们对数组中的 n 个元素中的每一个都执行了这两个操作，因此处理所有元素的总时间复杂度为 O(n log n)。

空间复杂度

可以通过考虑算法各个组件使用的内存来分析基于 Fenwick 树的解决方案的空间复杂度。

• 输入数组
  arr 的元素构成 n 个输入。这需要 O(n) 空间。
• 坐标压缩
  我们将压缩索引的内容映射到一个映射（或数组），其中每个唯一元素映射到其对应的压缩索引。最坏情况下，唯一元素的数量最多为 n，因此压缩索引存储需要 O(n) 空间。
• Fenwick 树（二叉索引树）
  Fenwick 树存储每个索引的累积频率。Fenwick 树数组需要 O(n) 空间，因为树的大小由压缩索引的范围决定，最多为 n。
• 临时变量
  该过程使用一些额外的变量（如查询和更新中使用的），但只需要常量空间 O(1)。
  最后，空间复杂度是输入数组、坐标压缩和 Fenwick 树所需空间的总和。所有这些组件都可以以 O(n) 空间运行，因为它们不重叠（加起来是 O(n²) 空间），这意味着最终的空间复杂度为 O(n)。