Leetcode 1365:有多少小于当前数字的数字(超详细的解法!!!)
发布日期:2021-06-29 15:58:42
浏览次数:2
分类:技术文章
本文共 1415 字,大约阅读时间需要 4 分钟。
给你一个数组 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
解题思路
数据量比较小,所以直接暴力解可以过。
class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: res, n = [], len(nums) for i in range(n): cnt = 0 for j in range(n): if nums[j] < nums[i]: cnt += 1 res.append(cnt) return res
也可以想到先排序,得到排序后的数组sorted_nums
,然后遍历nums
原数组中的元素i
,通过二分法查找i
在sorted_nums
中的位置即可知道有多少个元素比起小了。
class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: sorted_nums = sorted(nums) return [bisect.bisect_left(sorted_nums, num) for num in nums]
由于nums[i]<=100
,所以我们可以采用基数排序的思想,先统计所有元素出现的次数,然后计算所有出现次数的前缀和数组pre
,那么比第i
个元素小的元素个数就是pre[i - 1]
。
class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: cnt = collections.Counter(nums) for i in range(1, 101): cnt[i] += cnt[i - 1] return [cnt[x - 1] for x in nums]
我将该问题的其他语言版本添加到了我的
如有问题,希望大家指出!!!
转载地址:https://coordinate.blog.csdn.net/article/details/104595046 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月29日 13时38分22秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
自我学习39:接口自动化测试用例&功能测试用例区别
2019-04-29
mirror去兔子补丁下载 附安装教程
2019-04-29
mirror去兔子补丁 v3.0附安装教程
2019-04-29
mirror去兔子补丁为什么还有兔子_mirror去兔子补丁使用教程
2019-04-29
3dmax2012安装教程
2019-04-29
OC渲染器(Octane Render)整合版安装包 附安装教程
2019-04-29
操作系统期末大题复习
2019-04-29
hive:分区表,hbase外表
2019-04-29
想要成为运维,想要成为后期的架构师?这些知识是必备的!
2019-04-29
linux 是如何 快速一键安装禅道的呐?
2019-04-29
运维面试基础试题(四)
2019-04-29
一键安装Openstack单节点 必能成功
2019-04-29
面试紧张怎么办
2019-04-29
关系型数据库 ,nosql数据库简介
2019-04-29
Centos 7搭建NTP时间同步服务器
2019-04-29
centos7 基于rsync+inotify 实现定时备份
2019-04-29
指定IP进行 文件的分发
2019-04-29
基于http搭建本地yum仓库
2019-04-29
常规邮件基础
2019-04-29
邮件基础之 -- SMTP协议
2019-04-29