利用PHP计算有多少小于当前数字的数字方法示例
给你一个数组 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−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。
代码
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;
}
}
参考链接
总结
到此这篇关于利用PHP计算有多少小于当前数字的数字的文章就介绍到这了,更多相关PHP计算小于当前数字内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
php数字游戏 计算24算法
算法思路:把每一个数字看做一个独立的数学表达式,表达式之间加上标点符号组合成新表达式,一共组合4次,表达式之间的所有组合可以通过递归来实现. 代码如下: 复制代码 代码如下: <?php /** * A 24 maker * @version 1.0.0 * @author laruence<laruence at yahoo.com.cn> * @copyright (c) 2009 http://www.laruence.com */ class TwentyFourCal { pu
-
php用正则判断是否为数字的方法
前两天朋友的一个网站上有人利用php注入提交flash游戏分数,后来找原因才发现是有一位参数没有做数字判断导致. 本来保存游戏分数是 game.php?ac=save&fgid=1这个形式来实现,在php网页里面fgid直接调用,没有做任何的过滤.很多人利用在fgid=1后面加一个字母(fgid=1a),来实现一些非法操作. 假如 gamlist table 里面有一个游戏 fgid为102 select gname from gamelist where fgid='102′; selec
-
php 快速判断一个数字属于什么范围的实现方法
需求是这样 ... if ( $foo > 0 && $foo < 100 ) $bar = 1; elseif ( $foo > 99 && $foo < 212 ) $bar = 2; elseif ( $foo > 211 && $foo < 324 ) $bar = 3; elseif ( $foo > 323 && $foo < 382 ) $bar = 4; elseif ( $fo
-
PHP 计算至少是其他数字两倍的最大数的实现代码
计算至少是其他数字两倍的最大数 在一个给定的数组nums中,总是存在一个最大元素 . 查找数组中的最大元素是否至少是数组中每个其他数字的两倍. 如果是,则返回最大元素的索引,否则返回-1. 示例 1: 输入: nums = [3, 6, 1, 0] 输出: 1 解释: 6是最大的整数, 对于数组中的其他整数, 6大于数组中其他元素的两倍.6的索引是1, 所以我们返回1. 示例 2: 输入: nums = [1, 2, 3, 4] 输出: -1 解释: 4没有超过3的两倍大, 所以我们返回 -1.
-
php判断输入是否是纯数字，英文，汉字的方法
本文实例讲述了php判断输入是否是纯数字,英文,汉字的方法.分享给大家供大家参考.具体分析如下: 这里利用php的mb_strlen和strlen函数就可以轻松得知字符串的构成是全英文.英汉混合.还是纯汉字.简要说明如下: 1.如果strlen返回的字符长度和mb_strlen以当前编码计算的长度一 致,可以判断是纯英文字符串. 2.如果strlen返回的字符长度和mb_strlen以当前编码计算的长度不一致, 且strlen返回值同mb_strlen的返回值求余后得0可以判断为是全汉字的字符串
-
利用PHP计算有多少小于当前数字的数字方法示例
给你一个数组 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]=
-
JS操作字符串转数字的常见方法示例
本文实例讲述了JS操作字符串转数字的常见方法.分享给大家供大家参考,具体如下: JS中字符串转数字共三种方法 一.转换函数 JS提供了两个转换函数 parseInt() 换成整数 parseFloat()转换成浮点数 以上两个方法只针对String类型:对其他类型返回的都是NaN(Not a Number) parseInt("123abc");// 123 parseInt("oxA");// 10 parseInt("22.0");// 22
-
Python计算两个日期相差天数的方法示例
本文实例讲述了Python计算两个日期相差天数的方法.分享给大家供大家参考,具体如下: #!/usr/bin/python import time import sys def dateinput(): date = raw_input('please input the first date: ') return date def datetrans(tdate): spdate = tdate.replace("/","-") try: datesec = ti
-
Java计算交集，差集，并集的方法示例
本文实例讲述了Java计算交集,差集,并集的方法.分享给大家供大家参考,具体如下: package math; import java.util.HashSet; import java.util.Set; public class Test { public static void main(String[] args) { Set<Integer> result = new HashSet<Integer>(); Set<Integer> set1 = new Ha
-
利用swift实现卡片横向滑动动画效果的方法示例
本文主要给大家介绍了关于利用swift实现卡片横向滑动动画效果的相关资料,分享出来供大家参考学习,下面来一起看看详细的介绍吧. 根据惯例,首先上效果图: 那天去面试,面试官突然拿出手机点开了一个app,自个在那点了一会,然后问我 这个效果怎么实现,当时一看可以滑动,肯定用scrollView 或者 collectionView实现,就大概的说了下.今天刚好闲下来,就敲一敲这个效果. 先来分析下这个效果: 卡片是横向滚动,并且每个卡片的位置都是保持在屏幕中间的,而且 左右相邻的卡片都露出来一点边
-
Android利用Paint自定义View实现进度条控件方法示例
前言 View的三大流程:测量,布局,绘制,自定义View学的是啥?无非就两种:绘制文字和绘制图像. 我们在上一篇文章<Android绘图之Paint的使用>中学习了Paint的基本用法,但是具体的应用我们还没有实践过.从标题中可知,本文是带领读者使用Paint,自定义一个进度条控件. 效果图 上图就是本文要实现的效果图. 实现过程 既然是自定义控件,本文的该控件是直接继承View,然后重写View的onMeasure和onDraw方法来实现.其中onMeasure主要作用是测量控件的宽/高.
-
利用JavaScript为句子加标题的3种方法示例
前言 本文基于Free Code Camp基本算法脚本"标题案例一句". 在此算法中,我们要更改文本字符串,以便每个单词的开头始终都有一个大写字母. 在本文中,我将解释三种方法.首先使用FOR循环,其次使用map()方法,第三次使用replace()方法. 算法挑战 返回提供的字符串,每个单词的首字母大写.确保单词的其余部分为小写. 出于此练习的目的,你还应该大写连接词,例如" the"和" of". 提供的测试用例 titleCase(&quo
-
利用python实现命令行有道词典的方法示例
前言 由于一直用Linux系统,对于词典的支持特别不好,对于我这英语渣渣的人来说,当看英文文档就一直卡壳,之前用惯了有道词典,感觉很不错,虽然有网页版的但是对于全站英文的网页来说并不支持.索性自己实现一个,基于Python编写的小工具实现有道词典,思路也很简单,直接调用有道的api,解析下返回的json就ok了. 只用到了python原生的库,支持python2和python3. 示例代码 #!/usr/bin/env python # -*- coding:utf-8 -*- # API ke
-
利用C语言实现“百马百担”问题方法示例
前言 百马百担问题,有100匹马,驮100担货,大马驮3担,中马驮2担,两匹小马驮1担,问共有多少种驮法?且各种驮法中大.中.小马各多少匹? [分析] 1.定义整型变量m.n.k分别存放大马匹数.中马匹数.小马匹数: 2.定义整型变量sum存放共有几种驮法,且sum赋初值为0: 3.根据题意,大马.中马.小马共100匹:大马.中马.小马驮100担货满足如下关系: m+n+k=100(匹) 3*m+2*n+1/2*k=100(担) 4.三个未知数,两个方程,此题有若干组解: 5.计算机求解此类问题
-
利用vue组件自定义v-model实现一个Tab组件方法示例
前言 最近在学习vue,今天看到自定义组件,纠结了一会会然后恍然大悟...官方教程写得不是很详细,所以我决定总结一下.下面话不多说了,来一起看看详细的介绍吧. 效果 先让我们看一下例子的效果吧! v-model 我们知道 v-model 是 vue 里面的一个指令,vue的v-model是一个十分强大的指令,它可以自动让原生表单组件的值自动和你选择的值绑定,它可以用在 input 标签上,来做数据的双向绑定,就像这样: <input v-model="tab"> v-mod