1 条题解
-
0
题目目标是:对于每只鱼,计算它左边有多少只鱼的可爱程度小于它自己的可爱程度。由于鱼头朝左,每只鱼只能看到左边的鱼,因此只需检查它左侧的所有鱼。
算法原理:对每只鱼,从它左侧的第一个鱼开始,逐个检查其可爱程度是否小于当前鱼的可爱程度。若小于,则计数加一。所有鱼重复此过程。
具体步骤:
- 读取鱼的总数 和每只鱼的可爱程度数组 。
- 对于第 只鱼(从左到右,索引从 0 开始):
- 初始化计数器 。
- 从 到 (即所有左侧鱼)循环:
- 如果 ,则 相加 1。
- 将 作为第 只鱼的输出结果。
- 输出所有结果,用空格分隔。
走一个小例子: 输入为: 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,与样例一致。
边界情况:
- 当 时,只有鱼自己,左边没有鱼,结果为 0。
- 当所有鱼可爱程度相同,如全部为 3,则每只鱼左边的鱼都不小于它,结果全为 0。
- 数组可能有重复值,但题目中说明“小于”,所以相等不算。
时间复杂度:,外层循环 次,内层最多循环 次,总操作数为 ,近似 。 空间复杂度:,仅存储输入和输出数组。
- 1