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

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

1. 题目描述

在这里插入图片描述

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;
        }