题目
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
示例 2：
输入：nums = [-1]
输出：[0]
示例 3：
输入：nums = [-1,-1]
输出：[0,0]
参数范围
1 <= nums.length <= 105
-104 <= nums[i] <= 104
2023年3月版
用的树状数组
template class CTreeArr { public: CTreeArr(int iSize) :m_vData(iSize+1) { } void Add(int index, T value) { index++; while (index < m_vData.size()) { m_vData[index] += value; index += index&(-index); } } T Sum(int index) { index++; T ret = 0; while (index ) { ret += m_vData[index]; index -= index&(-index); } return ret; } private: vector m_vData; }; class Solution { public: vector countSmaller(vector& nums) { int iMin = *std::min_element(nums.begin(), nums.end()); for (auto& n : nums) { n -= iMin; } int iMax = *std::max_element(nums.begin(), nums.end()); CTreeArr treeArr(iMax + 1); vector vRet(nums.size()); for (int i = nums.size() - 1; i >= 0; i–) { vRet[i] = treeArr.Sum(nums[i] - 1); treeArr.Add(nums[i],1); } return vRet; } };
2023年8月 归并排序
class CMergeSortIndex { public: CMergeSortIndex(const vector& nums):m_nums(nums) { m_c = nums.size(); m_vIndexs.resize(nums.size()); iota(m_vIndexs.begin(), m_vIndexs.end(), 0); } void SortIndex( int left, int right) { if (right - left <= 1) { return; } const int mid = left + (right - left) / 2; SortIndex( left, mid); SortIndex( mid, right); //nums的[left,mid) 和[mid,right)分别排序 vector vIndexs; int i1 = left, i2 = mid; while ((i1 < mid) && (i2 < right)) { if (m_nums[m_vIndexs[i1]] > m_nums[m_vIndexs[i2]]) { vIndexs.emplace_back(m_vIndexs[i2++]); } else { vIndexs.emplace_back(m_vIndexs[i1]); OnAdd1(i1++, i2, left, mid, right); } } while (i1 < mid) { vIndexs.emplace_back(m_vIndexs[i1]); OnAdd1(i1++, i2, left, mid, right); } while (i2 < right) { vIndexs.emplace_back(m_vIndexs[i2++]); } for (int i = 0; i < vIndexs.size(); i++) { m_vIndexs[i + left] = vIndexs[i]; } } vector Sort() { SortIndex(0, m_c); vector vRet(m_c); for (int i = 0; i < m_c; i++) { vRet[i] = m_nums[m_vIndexs[i]]; } return vRet; } protected: virtual void OnAdd1(int i1, int i2, int left, int mid, int right) = 0; int m_c; const vector& m_nums; vector m_vIndexs; }; class CCountSmalle : public CMergeSortIndex { public: CCountSmalle(const vector& nums):CMergeSortIndex(nums) { m_vRet.resize(m_c); } vector m_vRet;
// 通过 CMergeSortIndex 继承 virtual void OnAdd1(int i1, int i2, int left, int mid, int right) override { m_vRet[m_vIndexs[i1]] += i2 - mid; }
}; class Solution { public: vector countSmaller(vector& nums) { CCountSmalle test(nums); auto tmp = test.Sort(); return test.m_vRet; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 鄙人想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
