【LeetCode每日一题】——1365.有多少小于当前数字的数字

这篇具有很好参考价值的文章主要介绍了【LeetCode每日一题】——1365.有多少小于当前数字的数字。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一【题目类别】

  • 排序

二【题目难度】

  • 简单

三【题目编号】

  • 1365.有多少小于当前数字的数字

四【题目描述】

  • 给你一个数组 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 < = n u m s . l e n g t h < = 500 2 <= nums.length <= 500 2<=nums.length<=500
  • 0 < = n u m s [ i ] < = 100 0 <= nums[i] <= 100 0<=nums[i]<=100

七【解题思路】

  • 利用计数排序的思想来解决这道题目
  • 首先使用count数组来保存每个数字出现的次数
  • 然后再次使用count数组来计算小于当前数字和个数和当前数字个数的和
  • 对于第i个数字,count[i-1]的值就是小于第i个数字的数字个数
  • 需要注意要对数字0进行特殊处理,否则会出现负的索引下标,从而出错
  • 最后返回结果即可

八【时间频度】

  • 时间复杂度: O ( n + k ) O(n+k) O(n+k) n n n为传入的数组的长度, k k k为传入的数组的值域大小
  • 空间复杂度: O ( k ) O(k) O(k) k k k为传入的数组的值域大小

九【代码实现】

  1. Java语言版
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] count = new int[101];
        int n = nums.length;
        for(int i = 0; i < n;i++){
            count[nums[i]]++;
        }
        for(int i = 1; i < 101;i++){
            count[i] += count[i - 1];
        }
        int[] res = new int[n];
        for(int i = 0;i < n;i++){
            res[i] = nums[i] == 0 ? 0 : count[nums[i] - 1];
        }
        return res;
    }
}
  1. C语言版
int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize)
{
    int* count = (int*)calloc(101, sizeof(int));
    int n = numsSize;
    for(int i = 0;i < n;i++)
    {
        count[nums[i]]++;
    }
    for(int i = 1;i < 101;i++)
    {
        count[i] += count[i - 1];
    }
    int* res = (int*)calloc(n, sizeof(int));
    for(int i = 0;i < n;i++)
    {
        res[i] = nums[i] == 0 ? 0 : count[nums[i] - 1];
    }
    *returnSize = n;
    return res;
}
  1. Python语言版
class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        n = len(nums)
        count = [0] * 101
        for i in range(0, n):
            count[nums[i]] += 1
        for i in range(1, 101):
            count[i] += count[i - 1]
        res = [0] * n
        for i in range(0, n):
            res[i] = 0 if nums[i] == 0 else count[nums[i] - 1]
        return res
  1. C++语言版
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> count(101, 0);
        int n = nums.size();
        for(int i = 0;i < n;i++){
            count[nums[i]]++;
        } 
        for(int i = 1; i < 101;i++){
            count[i] += count[i - 1];
        }
        vector<int> res(n, 0);
        for(int i = 0;i < n;i++){
            res[i] = nums[i] == 0 ? 0 : count[nums[i] - 1];
        }
        return res;
    }
};

十【提交结果】

  1. Java语言版
    【LeetCode每日一题】——1365.有多少小于当前数字的数字,LeetCode,算法,数据结构,LeetCode,排序,有多少小于当前数字的数字

  2. C语言版
    【LeetCode每日一题】——1365.有多少小于当前数字的数字,LeetCode,算法,数据结构,LeetCode,排序,有多少小于当前数字的数字

  3. Python语言版
    【LeetCode每日一题】——1365.有多少小于当前数字的数字,LeetCode,算法,数据结构,LeetCode,排序,有多少小于当前数字的数字

  4. C++语言版
    【LeetCode每日一题】——1365.有多少小于当前数字的数字,LeetCode,算法,数据结构,LeetCode,排序,有多少小于当前数字的数字文章来源地址https://www.toymoban.com/news/detail-681795.html

到了这里,关于【LeetCode每日一题】——1365.有多少小于当前数字的数字的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023-09-05 LeetCode每日一题(从两个数字数组里生成最小数字)

    点击跳转到题目位置 给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2 ,每个数组中的元素 互不相同 ,请你返回 最小 的数字,两个数组都 至少 包含这个数字的某个数位。 示例 1: 示例 2: 提示: 1 = nums1.length, nums2.length = 9 1 = nums1[i], nums2[i] = 9 每个数组中,元素 互不相

    2024年02月09日
    浏览(59)
  • 【LeetCode每日一题】单调栈 402 移掉k位数字

    402. 移掉 K 位数字 给你一个以字符串表示的非负整数 num 和一个整数 k ,移除这个数中的 k **位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。 示例 1 : 如果有 m+1 位数字,S1 a 0 a 1 a 2 . . . . a m a_0a_1a_2....a_m a 0 ​ a 1 ​ a 2 ​ .... a m ​ 需要去掉n位数字,

    2024年02月20日
    浏览(31)
  • Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的

    2024年02月14日
    浏览(39)
  • (数组与矩阵) 剑指 Offer 03. 数组中重复的数字 ——【Leetcode每日一题】

    难度:简单 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输入 : [2, 3, 1, 0, 2, 5, 3] 输出 :2 或

    2024年02月16日
    浏览(38)
  • (位运算) 1356. 根据数字二进制下 1 的数目排序 ——【Leetcode每日一题】

    难度:简单 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。 如果存在多个数字二进制中 1 的数目相同,则必须将它们按照数值大小升序排列。 请你返回排序后的数组。 示例 1: 输入 :arr = [0,1,2,3,4,5,6,7,8] 输出 :[0,1,2,4,8,3,5,6,7] 解释

    2024年02月12日
    浏览(47)
  • 2023年7月3日leetcode每日一题打卡——136.只出现一次的数字

    136. 只出现一次的数字 - 力扣(LeetCode) 给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现 线性时间复杂度 的算法来解决此问题,且该算法 只使用常量额外空间 。 示例1: 示例2: 示

    2024年02月12日
    浏览(40)
  • LeetCode[315]计算右侧小于当前元素的个数

    难度:Hard 题目: 给你一个整数数组  nums   ,按要求返回一个新数组  counts   。数组  counts  有该性质:  counts[i]  的值是  nums[i]  右侧小于  nums[i]  的元素的数量。  示例 1:   示例 2:   示例 3: 提示: 1 = nums.length = 105 -104 = nums[i] = 104  Related Topics 树状数组 线段树

    2024年02月15日
    浏览(34)
  • 【LeetCode】每日一题&最后一个单词的长度&投票法求解多数元素&异或操作符巧解只出现一次的数字&整数反转

    ========================================================================= 个人主页直达: 小白不是程序媛 LeetCode系列专栏: LeetCode刷题掉发记 ========================================================================= 目录 LeetCode 58.最后一个单词的长度 LeetCode169.多数元素 LeetCode 136.出现一次的数字 LeetCode 7.整数

    2024年02月08日
    浏览(46)
  • C++归并排序算法的应用:计算右侧小于当前元素的个数

    给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 示例 1: 输入:nums = [5,2,6,1] 输出:[2,1,1,0] 解释: 5 的右侧有 2 个更小的元素 (2 和 1) 2 的右侧仅有 1 个更小的元素 (1) 6 的右侧有 1 个更小的元

    2024年02月06日
    浏览(36)
  • 二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”

    各位CSDN的uu们你们好呀,今天小雅兰的内容仍然是二叉树和Leetcode每日一题,下面,就让我们进入二叉树的世界吧!!! 这个题目需要重新定义一个函数,函数参数需要有左子树和右子树,题目所给定的函数无法解决问题。 每个不为空的结点,都可以认为是一棵子树的根 

    2024年02月16日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包