1 条题解

  • 0
    @ 2026-10-17 3:52:03

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

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

    具体步骤:

    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),仅存储输入和输出数组。

    • 1

    信息

    ID
    78
    时间
    1000ms
    内存
    128MiB
    难度
    进阶
    标签
    递交数
    2
    已通过
    1
    上传者