给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。
换而言之,对于每个 nums[i] 你必须计算出有效的 j 的数量,其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
示例 1:
输入:nums = [8,1,2,2,3]
输出:[4,0,1,1,3]
解释:
对于 nums[0]=8 存在四个比它小的数字:(1,2,2 和 3)。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字:(1)。
对于 nums[3]=2 存在一个比它小的数字:(1)。
对于 nums[4]=3 存在三个比它小的数字:(1,2 和 2)。
示例 2:
输入:nums = [6,5,4,8]
输出:[2,1,0,3]
示例 3:
输入:nums = [7,7,7,7]
输出:[0,0,0,0]
提示:
- 2 <= nums.length <= 500
- 0 <= nums[i] <= 100
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number
解题思路 1
枚举数组里的每个数字,遍历数组统计有多少数字比当前数字小即可
代码
class Solution { /** * @param Integer[] $nums * @return Integer[] */ function smallerNumbersThanCurrent($nums) { $count = count($nums); $result = array_fill(0, $count, 0); for ($i = 0; $i < $count; $i++) { for ($j = 0; $j < $count; $j++) { if ($nums[$j] < $nums[$i]) { $result[$i]++; } } } return $result; } }
解题思路 2 - 频次数组+前缀和
注意到数字的值域范围为 [0,100][0,100] ,所以可以考虑建立一个频次数组 cnt[i]cnt[i] ,表示数字 ii 出现的次数,那么对于数字 ii 而言,它的答案:即小于它的数字出现个数之和,直接算需要遍历 [0,i-1][0,i"htmlcode">
class Solution { /** * @param Integer[] $nums * @return Integer[] */ function smallerNumbersThanCurrent($nums) { $count = count($nums); $cnt = array_fill(0, 101, 0); // 填充 0 的计数数组 $result = array_fill(0, $count, 0); // 填充 0 的结果数组 // $nums 中出现的值和数量对应落到 $cnt 中 foreach ($nums as $num) { $cnt[$num]++; } // $cnt 转化成 $i 的值是 sum($cnt[0], .. $cnt[$i - 1]) 新数组,即为小于 $i 的数据数量 foreach (range(1, 100) as $i) { $cnt[$i] += $cnt[$i - 1]; } // 结果数组中出现的 索引值 替换为 计数数组中的 数量 foreach (range(0, $count - 1) as $i) { if ($nums[$i]) { $result[$i] = $cnt[$nums[$i] - 1]; } } return $result; } }
参考链接
leetcode 官方题解
总结
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
RTX 5090要首发 性能要翻倍!三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB,每个模块容量为2GB。其速度预设为32 Gbps(PAM3),但也可以降至28 Gbps,以提高产量和初始阶段的整体性能和成本效益。
据三星表示,GDDR7内存的能效将提高20%,同时工作电压仅为1.1V,低于标准的1.2V。通过采用更新的封装材料和优化的电路设计,使得在高速运行时的发热量降低,GDDR7的热阻比GDDR6降低了70%。
更新日志
- [吉他演奏]RCAREDSEAL《Rodrigo-ConciertoDeAranjues》[WAV+CUE]
- 气质绝了!《黑神话》蜘蛛四妹演员COS自己正片释出
- 《黑神话:悟空》第五章动画大闹天宫内容被删:牛魔王是主角
- 玩家吐槽《黑神话》如意金箍棒属性差:就该是最强武器
- 《邓紫棋 上古情歌2CD》[WAV/分轨][1.1GB]
- 崔健《摇滚交响音乐会 2CD》[WAV/分轨][730MB]
- 群星《顶级发烧大碟 蒙面歌王争霸战 2CD》[WAV/分轨][1.3GB]
- 群星.2009-原班情歌2CD【SONY】【WAV+CUE】
- 群星.2024-长乐曲电视剧原声带【TME影音】【FLAC分轨】
- 群星.1993-烧得厉害VOL.1好戏好歌唱不停【滚石】【WAV+CUE】
- 魔兽世界wlk阿奴巴拉克怎么打 wlk阿奴巴拉克机制与打法
- 归龙潮阿律的笛子位置在哪 阿律的笛子图文位置一览
- 归龙潮中浦城区福鼠位置在哪 中浦城区福鼠收集位置大全
- NewViennaOctetViennaWindSoloists-TheDeccaRecordings(2024)18CD[24-48][FLAC]-9
- MatteoPasqualini-JohannSebastianBachItalienischesKonzertFranzsischeOuvertureVierDue