[leetcode] 1365. How Many Numbers Are Smaller Than the Current Number

[leetcode] 1365. How Many Numbers Are smaller than the Current Number

Description

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j’s such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]Output: [4,0,1,1,3]Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). For nums[1]=1 does not exist any smaller number than it.For nums[2]=2 there exist one smaller number than it (1). For nums[3]=2 there exist one smaller number than it (1). For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:

Input: nums = [6,5,4,8]Output: [2,1,0,3]

Example 3:

Input: nums = [7,7,7,7]Output: [0,0,0,0]

Constraints:

2 <= nums.length <= 5000 <= nums[i] <= 100

分析

题目的意思是：给你一个数组，统计比当前数小的数的个数，首先用了pos字典把所有的坐标存放了下来，然后对原来的数据进行了排序，然后遍历排序的数组就能很容易得到结果了。看别人的代码发现有比这更好的思路，首先用sorted排序，用字典存放比当前数小的个数，最后把统计结果放回到对应的位置就行了。

代码

class Solution: def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]: s=[] res=[0]*len(nums) pos=collections.defaultdict(list) for i in range(len(nums)): pos[nums[i]].append(i) nums.sort() for num in nums: cnt=len(s) while(len(pos[num])>0): res[pos[num].pop()]=cnt s.append(num) return res

参考文献

​​[LeetCode] Python 3 -> 88.46% faster. 56ms time. Explanation added​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。