【深基5.例1】小鱼比可爱 · 教师题解

题目目标是:对于每只鱼,计算它左边有多少只鱼的可爱程度小于它自己的可爱程度。由于鱼头朝左,每只鱼只能看到左边的鱼,因此只需检查它左侧的所有鱼。

算法原理:对每只鱼,从它左侧的第一个鱼开始,逐个检查其可爱程度是否小于当前鱼的可爱程度。若小于,则计数加一。所有鱼重复此过程。

具体步骤:

  1. 读取鱼的总数 nn 和每只鱼的可爱程度数组 aa。
  2. 对于第 ii 只鱼(从左到右,索引从 0 开始):
    • 初始化计数器 count=0count = 0。
    • 从 j=0j = 0 到 j=i−1j = i-1(即所有左侧鱼)循环:
      • 如果 a[j]<a[i]a[j] < a[i],则 countcount 相加 1。
    • 将 countcount 作为第 ii 只鱼的输出结果。
  3. 输出所有结果,用空格分隔。

走一个小例子: 输入为: 6 4 3 0 5 1 2

逐个计算每只鱼:

  • 第 0 只鱼(可爱程度 4):左边无鱼,所以结果是 0。
  • 第 1 只鱼(可爱程度 3):左边只有 4,4 ≥ 3,不小于,所以结果是 0。
  • 第 2 只鱼(可爱程度 0):左边是 4 和 3,都大于 0,都不小于,结果是 0。
  • 第 3 只鱼(可爱程度 5):左边是 4、3、0,这三个都小于 5,所以结果是 3。
  • 第 4 只鱼(可爱程度 1):左边是 4、3、0、5,其中只有 0 小于 1,所以结果是 1。
  • 第 5 只鱼(可爱程度 2):左边是 4、3、0、5、1,其中 0 和 1 小于 2,所以结果是 2。

输出:0 0 0 3 1 2,与样例一致。

边界情况:

  • 当 n=1n = 1 时,只有鱼自己,左边没有鱼,结果为 0。
  • 当所有鱼可爱程度相同,如全部为 3,则每只鱼左边的鱼都不小于它,结果全为 0。
  • 数组可能有重复值,但题目中说明“小于”,所以相等不算。

时间复杂度:O(n2)O(n^2),外层循环 nn 次,内层最多循环 nn 次,总操作数为 n(n−1)/2n(n-1)/2,近似 O(n2)O(n^2)。 空间复杂度:O(n)O(n),仅存储输入和输出数组。

返回题目