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

发表于： 分类于：
字数： 878 阅读：≈ 2分钟

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

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i]

以数组形式返回答案。

思路

基本思想

相比于单调栈，本题中求的是所有比自己小的元素，可以用暴力算法，依次拿数组中的每一个元素去和数组中每一个元素比较，从而统计得到结果，此时需要双层循环，代码为:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> ans(nums.size(),0);
        for(int i=0;i<nums.size();++i){
            for(int j=0;j<nums.size();++j){
                //找到比自己小的元素
                if(nums[i]>nums[j]){
                    ans[i]+=1;
                }
            }
        }
        return ans;
    }
};

为了减少运行的时间复杂度，可以先对元素进行升序排序，这样小于自己的都在自己的前面，并且当前元素的下标就代表了前面有几个小于自己的元素

但是有一个特殊情况：

image-20230704215655447

当两个数字相同时，第一个2的下标为1，代表前面有一个比自己小的元素，符合要求，但是第二个2的下标为2，代表前面有两个比自己小的元素，显然有错误

所以可以从后向前遍历，这样第二个二的结果就会被第一个二覆盖，形成正确的结果

知道每个元素有几个比自己小的元素之后，还需要调整位置，不能以排序之后的位置提交代码

相当于先对nums进行排序，并且nums原有的顺序要有记录

执行流程

  1. 定义一个新的vector存储nums中的数据，对这个vector排序，防止nums中的元素顺序改变
  2. 定义一个unordered_map，用来存储每个元素有几个小于自己的元素，当成一个字典
  3. 为了形成最终的结果，不能直接使用排序后统计的结果，所以还需要调整顺序

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> ans(nums.size(),0);
        vector<int> vec=nums;
        sort(vec.begin(),vec.end());
        unordered_map<int,int>temp;
        for(int i=vec.size()-1;i>=0;--i){
            //代表元素nums[i]前面有i个小于自己的元素
            temp[vec[i]]=i;
        }
        //调整位置，将temp当成一个字典
        //使用unordered_map效率更高
        for(int i=0;i<nums.size();++i){
            ans[i]=temp[nums[i]];
        }
        return ans;
    }
};

总结

对元素进行排序，从而巧妙的得到有几个元素比自己小，遇到相同的元素时，从后向前遍历，可以覆盖错误的结果，所以也是一个技巧

并且最终要求的结果是不能排序的，所以还需要调整结果的顺序，所以不能直接对nums的数据排序，需要单独定义一个vector来排序