力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字

简介: 力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字

(一)题目描述

给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。

换而言之,对于每个 nums[i] 你必须计算出有效的 j 的数量,其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

来源:力扣(LeetCode

链接:https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

(二)输入、输出示例

示例 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]
• 1
• 2

示例 3:

输入:nums = [7,7,7,7]
输出:[0,0,0,0]

(三)代码实现

方法1(php版):

解题思路

最笨的方法,双层循环,遍历判断。但耗费时间较长,O(n²)时间复杂度

代码实现

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function smallerNumbersThanCurrent($nums) {
        $return = [];
        foreach ($nums as $k_1 => $v_1){
            $num = 0;
            foreach ($nums as $k_2 => $v_2){
                if($v_2 < $v_1){
                    $num++;
                }
            }
            $return[$k_1] = $num;
        }
        return $return;
    }
}

性能分析

运行时间 内存消耗
100ms 14.7 MB

方法2(php版):

解题思路

1.因为要判断某个元素比它小的有几个,那就先升序排列构造一个新数组。新数组中当前元素的key值,即为有多少个比他小的元素。如示例1中:[8,1,2,2,3]升序之后变成[1,2,2,3,8]。 元素8的key为4,即前面有4个元素比8小。

2.遍历元素,使用array_search根据值返回key(有多少个比当前值大的元素)即可。

代码实现

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function smallerNumbersThanCurrent($nums) {
        $sort_arr = $nums;
        sort($sort_arr);
        $return = [];
        foreach ($nums as $k => $v){
            $return[$k] = array_search($v, $sort_arr);
        }
        return $return;
    }
}

(四)性能分析

运行时间 内存消耗
8ms 14.8 MB
目录
相关文章
|
2天前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
22 4
|
8天前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
40 9
|
4月前
|
算法 容器
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
|
5月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
6月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
111 1
|
6月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
147 0
|
6月前
力扣(LeetCode)数据结构练习题(2)
力扣(LeetCode)数据结构练习题(2)
54 0
|
6月前
|
存储
力扣(LeetCode)数据结构练习题
力扣(LeetCode)数据结构练习题
92 0
|
14天前
|
存储 算法 调度
基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
本程序基于和声搜索优化算法(Harmony Search, HS),实现机器工作调度的MATLAB仿真,输出甘特图展示调度结果。算法通过模拟音乐家即兴演奏寻找最佳和声的过程,优化任务在不同机器上的执行顺序,以最小化完成时间和最大化资源利用率为目标。程序适用于MATLAB 2022A版本,运行后无水印。核心参数包括和声记忆大小(HMS)等,适应度函数用于建模优化目标。附带完整代码与运行结果展示。
|
7天前
|
算法 安全 数据安全/隐私保护
基于AES的遥感图像加密算法matlab仿真
本程序基于MATLAB 2022a实现,采用AES算法对遥感图像进行加密与解密。主要步骤包括:将彩色图像灰度化并重置大小为256×256像素,通过AES的字节替换、行移位、列混合及轮密钥加等操作完成加密,随后进行解密并验证图像质量(如PSNR值)。实验结果展示了原图、加密图和解密图,分析了图像直方图、相关性及熵的变化,确保加密安全性与解密后图像质量。该方法适用于保护遥感图像中的敏感信息,在军事、环境监测等领域具有重要应用价值。

热门文章

最新文章