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

Dear 丶 2022-11-28 00:42 105阅读 0赞

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

以数组形式返回答案。

2 <= nums.length <= 500  
0 <= nums\[i\] <= 100

法一：输入数组中最大数字为100，因此可以创建一个长度为101的以下标为键的哈希表，保存的是nums数组中比下标小的数字数，最后再遍历nums，从哈希表中直接取得比每个元素小的数字数：

class Solution { 
    public:
        vector<int> smallerNumbersThanCurrent(vector<int>& nums) { 
            int sz = nums.size();
            vector<int> res(sz);
            vector<int> ivec(101);
    
            for (int num : nums) { 
                ++ivec[num];
            }
    
            for (int i = 1; i <= 100; ++i) { 
                ivec[i] += ivec[i - 1];
            }
    
            for (int i = 0; i < sz; ++i) { 
                if (nums[i] == 0) {     // 比0小的数一定是0
                    res[i] = 0;
                    continue;
                }
                res[i] = ivec[nums[i] - 1];
            }
    
            return res;
        }
    };

此方法的空间复杂度为O（S），S为输入数字范围。时间复杂度为O（n+S），原因是遍历了一遍nums和ivec。适用于输入的数字范围S小的情况。

法二：暴力法：

class Solution { 
    public:
        vector<int> smallerNumbersThanCurrent(vector<int>& nums) { 
            int sz = nums.size();
            vector<int> res(sz);
    
            for (int i = 0; i < sz; ++i) { 
                for (int j = 0; j < sz; ++j) { 
                    if (nums[i] > nums[j]) { 
                    	++res[i];
                    }
                }
            }
            
            return res;
        }
    };

空间复杂度O（1），时间复杂度O（n2)。

法三：创建一个二元组数组，二元组为数字和数组下标，之后对二元组排序，现在二元组数组就是以数字从小到大排序的了，之后遍历二元组数组，用变量pre记录比当前数字小的数字个数：

class Solution { 
    public:
        vector<int> smallerNumbersThanCurrent(vector<int>& nums) { 
            int sz = nums.size();
            vector<pair<int,int>> tmp(sz);
    
            for (int i = 0; i < sz; ++i) { 
                tmp[i] = make_pair(nums[i], i);
            }
    
            sort(tmp.begin(), tmp.end());    // 按数字排序，相同数字的按数字所在下标排序
    
            int pre = 0;
            vector<int> res(sz);
            for (int i = 0; i < sz; ++i) { 
                if (i == 0) { 
                    res[tmp[i].second] = pre;    // 将结果放在数字tmp[i].first的原下标处
                } else if (tmp[i].first == tmp[i - 1].first) { 
                    res[tmp[i].second] = pre;
                } else { 
                    pre = i;
                    res[tmp[i].second] = pre;
                }
            }
            
            return res;
        }
    };

此方法的时间复杂度为O（nlogn），原因是排序时间复杂度为O（nlogn），遍历一遍tmp的时间复杂度为O（n）。空间复杂度为O（n），因为使用了tmp存放临时的二元组。