列表

详情

NC360. 右侧更小数

描述

给定一个长度为 n 的数组 nums ，请你返回一个新数组 count ，其中 count[i] 是 nums[i] 右侧小于 nums[i] 的元素个数。

数据范围： ，数组元素值满足

示例1

输入: 

[9,8,7,6,5]

输出: 

[4,3,2,1,0]

示例2

输入: 

[5,7,8,9,6]

输出: 

[0,1,1,1,0]

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 38ms, 内存消耗: 3804KB, 提交时间: 2022-03-14 

class Solution {
public:
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    void update(int x, vector<int> &tree, int y) {
        for(int i = x; i < tree.size(); i+=(i &(-i))) {
            tree[i] += y;
        }
    }
    int query(int x, vector<int> &tree) {
        int sum = 0;
        for(int i = x; i > 0; i-=(i &(-i))) {
            sum += tree[i];
        }
        return sum;
    }
    
    vector<int> smallerCount(vector<int>& nums) {
        int len = nums.size();
        vector<int> res(len, 0);
        vector<int> temp;
        temp.assign(nums.begin(), nums.end());
        sort(temp.begin(), temp.end());
        int l = unique(temp.begin(), temp.end()) - temp.begin();
        for (int i = 0; i < len; ++i) {
            nums[i] = lower_bound(temp.begin(), temp.begin() + l, nums[i]) - temp.begin() + 1;
        }
        
        vector<int> tree(len + 1, 0); 
        for (int i = len -1; i >= 0; --i){
            res[i] = query(nums[i] - 1, tree);
            update(nums[i], tree, 1);
        }
        return res;
    }
};

C++ 解法, 执行用时: 43ms, 内存消耗: 4476KB, 提交时间: 2022-04-15 

static const auto io_sync_off = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
  public:
    vector<int> index;
    vector<int> temp;
    vector<int> tempIndex;
    vector<int> ans;

    void Merge(vector<int>& a, int l, int mid, int r) {
        int i = l, j = mid + 1, p = l;
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) {
                temp[p] = a[i];
                tempIndex[p] = index[i];
                ans[index[i]] += (j - mid - 1);
                ++i;
                ++p;
            } else {
                temp[p] = a[j];
                tempIndex[p] = index[j];
                ++j;
                ++p;
            }
        }
        while (i <= mid) {
            temp[p] = a[i];
            tempIndex[p] = index[i];
            ans[index[i]] += (j - mid - 1);
            ++i;
            ++p;
        }

        while (j <= r) {
            temp[p] = a[j];
            tempIndex[p] = index[j];
            ++j;
            ++p;
        }

        for (int k = l; k <= r; ++k) {
            index[k] = tempIndex[k];
            a[k] = temp[k];
        }
    }

    void MergeSort(vector<int>& a, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) >> 1;
        MergeSort(a, l, mid);
        MergeSort(a, mid + 1, r);
        Merge(a, l, mid, r);
    }

    vector<int> smallerCount(vector<int>& nums) {
        index.resize(nums.size()); //存放原数组各元素对应的下标
        temp.resize(nums.size()); //原数组的副本
        tempIndex.resize(nums.size()); //存放副本数组各元素对应的下标
        ans.resize(nums.size()); //存放最终结果

        for (int i = 0; i < nums.size(); ++i) {
            index[i] = i;
        }

        int l = 0, r = nums.size() - 1;
        MergeSort(nums, l, r); //归并排序
        return ans;
    }
};

C++ 解法, 执行用时: 45ms, 内存消耗: 3752KB, 提交时间: 2022-07-06 

class Solution {
  public:
    void update(int x, vector<int>& tree, int y) {
        for (int i = x; i < tree.size(); i += (i & (-i))) {
            tree[i] += y;
        }
    }
    int query(int x, vector<int>& tree) {
        int sum = 0;
        for (int i = x; i > 0; i -= (i & (-i))) {
            sum += tree[i];
        }
        return sum;
    }
    vector<int> smallerCount(vector<int>& nums) {
        int h = nums.size();
        vector<int> z(h, 0);
        vector<int> v;
        v.assign(nums.begin(), nums.end());
        sort(v.begin(), v.end());
        int l = unique(v.begin(), v.end()) - v.begin();
        for (int i = 0; i < h; ++i) {
            nums[i] = lower_bound(v.begin(), v.begin() + l, nums[i]) - v.begin() + 1;
        }
        vector<int> tree(h + 1, 0);
        for (int i = h - 1; i >= 0; --i) {
            z[i] = query(nums[i] - 1, tree);
            update(nums[i], tree, 1);
        }
        return z;
    }
};

C++ 解法, 执行用时: 45ms, 内存消耗: 4520KB, 提交时间: 2022-07-11 

class Solution {
  public:
    vector<int> index;
    vector<int> temp;
    vector<int> tempIndex;
    vector<int> ans;

    void Merge(vector<int>& a, int l, int mid, int r) {
        int i = l, j = mid + 1, p = l;
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) {
                temp[p] = a[i];
                tempIndex[p] = index[i];
                ans[index[i]] += (j - mid - 1);
                ++i;
                ++p;
            } else {
                temp[p] = a[j];
                tempIndex[p] = index[j];
                ++j;
                ++p;
            }
        }
        while (i <= mid) {
            temp[p] = a[i];
            tempIndex[p] = index[i];
            ans[index[i]] += (j - mid - 1);
            ++i;
            ++p;
        }
        while (j <= r) {
            temp[p] = a[j];
            tempIndex[p] = index[j];
            ++j;
            ++p;
        }
        for(int k=l;k<=r;++k){
            a[k]=temp[k];
            index[k]=tempIndex[k];
        }
    }
    void mergeSort(vector<int>& a,int l,int r){
        if(l>=r) return;
        int mid=(l+r)>>1;
        mergeSort(a, l, mid);
        mergeSort(a,mid+1,r);
        Merge(a,l,mid,r);
    }
    
    vector<int> smallerCount(vector<int>& nums) {
        index.resize(nums.size()); //存放原数组各元素对应的下标
        temp.resize(nums.size()); //原数组的副本
        tempIndex.resize(nums.size()); //存放副本数组各元素对应的下标
        ans.resize(nums.size()); //存放最终结果
 
        for (int i = 0; i < nums.size(); ++i) {
            index[i] = i;
        }
 
        int l = 0, r = nums.size() - 1;
        mergeSort(nums, l, r); //归并排序
        return ans;
    }
};

C++ 解法, 执行用时: 46ms, 内存消耗: 3768KB, 提交时间: 2022-08-06 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    void update(int x,vector<int> &tree,int y)
    {
        for(int i=x;i<tree.size();i+=(i&(-i)))
        {
            tree[i]+=y;
        }
    }
    int query(int x,vector<int> &tree)
    {
        int sum=0;
        for(int i=x;i>0;i-=(i&(-i)))
        {
            sum+=tree[i];
        }
        return sum;
    }
    vector<int> smallerCount(vector<int>& nums) {
        int len=nums.size();
        vector<int> res(len,0);
        vector<int> temp;
        temp.assign(nums.begin(),nums.end());
        sort(temp.begin(),temp.end());
        int l=unique(temp.begin(),temp.end())-temp.begin();
        for(int i=0;i<len;++i)
        {
            nums[i]=lower_bound(temp.begin(), temp.begin()+l, nums[i])-temp.begin()+1;
        }
        vector<int> tree(len+1,0);
        for(int i=len-1;i>=0;--i)
        {
            res[i]=query(nums[i]-1,tree);
            update(nums[i],tree,1);
        }
        return res;
    }
};

上一题

© 2024 nowcoder.com