LeetCode 1365. 有多少小于当前数字的数字-蒲公英云

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

Dear 丶 2022-11-28 00:42 213阅读 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;
    }
};