利用PHP计算有多少小于当前数字的数字方法示例
给你一个数组nums，对于其中每个元素nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个nums[i]你必须计算出有效的j的数量，其中j满足j!=i且nums[j] 以数组形式返回答案。 示例1： 输入：nums=[8,1,2,2,3] 示例2： 输入：nums=[6,5,4,8] 示例3： 输入：nums=[7,7,7,7] 提示： 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number 解题思路1 枚举数组里的每个数字，遍历数组统计有多少数字比当前数字小即可 代码 解题思路2-频次数组+前缀和 注意到数字的值域范围为[0,100][0,100]，所以可以考虑建立一个频次数组cnt[i]cnt[i]，表示数字ii出现的次数，那么对于数字ii而言，它的答案：即小于它的数字出现个数之和，直接算需要遍历[0,i-1][0,i−1]的cntcnt求和，仍需要线性的时间去计算，但我们注意到这个答案是一个前缀和，所以我们可以再对cntcnt数组求前缀和。那么对于数字ii的答案就是cnt[i-1]cnt[i−1]，算答案的时间复杂度从O(n)O(n)降到了O(1)O(1)。 最后整个算法流程为：遍历数组元素，更新cntcnt数组，即cnt[nums[i]]+=1，然后对cntcnt数组求前缀和，最后遍历数组元素，对于相应的数字O(1)O(1)得到答案即可。 计数排序是一种特殊的桶排序，一般适用于排序数据长度n远大于种类k的情况。比如本题k=101,n=500,甚至5000。 代码 参考链接 leetcode官方题解 总结 到此这篇关于利用PHP计算有多少小于当前数字的数字的文章就介绍到这了,更多相关PHP计算小于当前数字内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！ 声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
输出：[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,1,0,3]
输出：[0,0,0,0]
classSolution{
/***@paramInteger[]$nums*@returnInteger[]*/
functionsmallerNumbersThanCurrent($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;
}
}
classSolution{
/***@paramInteger[]$nums*@returnInteger[]*/
functionsmallerNumbersThanCurrent($nums){
$count=count($nums);
$cnt=array_fill(0,101,0);//填充0的计数数组
$result=array_fill(0,$count,0);//填充0的结果数组
//$nums中出现的值和数量对应落到$cnt中
foreach($numsas$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;
}
}