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

雨点打透心脏的1/2处 2022-12-18 10:53 163阅读 0赞

# 1. 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]

# 2. 题目思路 #

*  给定一个数组，让你返回每个数值数组中比他小的个数
 *  思路一：直接暴力，两次for循环，出结果
 *  思路二：快速排序，`prev == -1 || data[i][0] != data[i - 1][0]`，如果当前的数值不等于前面的数值的话，说明不重复，进行`ret[data[i][1]] = prev;`
 *  思路三：桶排序，一遍循环放桶中，一遍循环求下前缀和，最后一遍得出结果`注意：因为该题目指定了规定的数据区间`

# 3. 题目代码 #

public static int[] SmallerNumbersThanCurrent(int[] nums)
            {
        
                // 桶排
                int[] array = new int[101];
                for (int i = 0; i < nums.Length; i++)
                {
        
                    array[nums[i]]++;
                }
                for (int i = 1; i < 101; i++)
                {
        
                    array[i] = array[i] + array[i - 1];
                }
    
                int[] cnt = new int[nums.Length];
                for (int i = 0; i < nums.Length; i++)
                {
        
                    if (nums[i] == 0)
                    {
        
                        cnt[i] = 0;
                    }
                    else
                    {
        
                        cnt[i] = array[nums[i] - 1];
                    }
                }
                return cnt;
            }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/51b1cdc911344300a5de1a633d365081.png