leetcode-315. Count of Smaller Numbers After Self

xiaoxiao2021-02-28  106

这道题好难,考察树状数组。 思路:首先,先判断nums是否为0数组,若是做出相应选择;然后将nums转化为从1开始的数组,即整体平移,使其最小值为1;然后构造树状数组tree,tree【i】的含义要搞清楚:从tree【i】加到i去尾到0的tree【0】为,当前数字num位置后面的, 比num小的数的个数之和。然后每移动一次要更新一次tree。

C++ 代码:

class Solution { public: vector<int> countSmaller(vector<int>& nums) { vector<int> ret; int min1 = INT_MAX, max1 = INT_MIN; int len = nums.size(); if (len == 0 ) return ret; for (auto i : nums) { min1 = min(min1, i); } for (int i=0; i<len; i++) { nums[i] = nums[i] - min1 + 1; max1 = max(max1, nums[i]); } int *tree = new int[max1+1]; memset(tree, 0, sizeof(int)*(max1+1)); for (int i=len -1; i>=0; i--) { add(ret, nums[i] - 1, tree); update(tree, nums[i], max1 + 1); } free(tree); return ret; } void add(vector<int> &ret, int num, int *tree) { int sum = 0; while (num > 0) { sum += tree[num]; num -= (num&(-num)); } ret.insert(ret.begin(), sum); } void update(int *tree, int num, int maxsize) { while (num < maxsize) { tree[num]++; num += num&(-num); } } };
转载请注明原文地址: https://www.6miu.com/read-62878.html

最新回复(0)