本文涉及知识点
离散化 树状树状
LeetCode 100246 将元素分配到两个数组中
给你一个下标从 1 开始、长度为 n 的整数数组 nums 。
现定义函数 greaterCount ，使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。
你需要使用 n 次操作，将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：
如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr1 。
如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr2 。
如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，将 nums[i] 追加到元素数量较少的数组中。
如果仍然相等，那么将 nums[i] 追加到 arr1 。
连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。
返回整数数组 result 。
示例 1：
输入：nums = [2,1,3,3]
输出：[2,3,1,3]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。
在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。
因此，连接形成的数组 result 是 [2,3,1,3] 。
示例 2：
输入：nums = [5,14,3,1,2]
输出：[5,3,1,2,14]
解释：在前两次操作后，arr1 = [5] ，arr2 = [14] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是一，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，arr1 中大于 1 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[4] 追加到 arr1 。
在第 5 次操作中，arr1 中大于 2 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[5] 追加到 arr1 。
在 5 次操作后，arr1 = [5,3,1,2] ，arr2 = [14] 。
因此，连接形成的数组 result 是 [5,3,1,2,14] 。
示例 3：
输入：nums = [3,3,3,3]
输出：[3,3,3,3]
解释：在 4 次操作后，arr1 = [3,3] ，arr2 = [3,3] 。
因此，连接形成的数组 result 是 [3,3,3,3] 。
提示：
3 <= n <= 105
1 <= nums[i] <= 109
预备知识
本题的数据最大109，如果不离散化，空间复杂度会超。
离散化：不改变各数值相对大小的前提下，尽可能得减小各数值。
比如：{3,7,7,8} 变成{1,2,2,3}。
树状数组，可以在O(logn)时间更新数值和求和。
代码
template<class ELE = int > class CTreeArr { public: CTreeArr(int iSize) :m_vData(iSize + 1) { } void Add(int index, ELE value) { index++; while (index < m_vData.size()) { m_vData[index] += value; index += index & (-index); } } ELE Sum(int index) { index++; ELE ret = 0; while (index) { ret += m_vData[index]; index -= index & (-index); } return ret; } ELE Get(int index) { return Sum(index) - Sum(index - 1); } private: vector<ELE> m_vData; }; class CTreeArrHlp { public: CTreeArrHlp(vector<int> nums) { sort(nums.begin(), nums.end()); nums.erase(std::unique(nums.begin(), nums.end()), nums.end()); for (int i = 0; i < nums.size(); i++) { mValueToIndex[nums[i]] = i; } m_pTreeArr = new CTreeArr<int>(nums.size()); } void Add(const int& val) { m_nums.emplace_back(val); m_pTreeArr->Add(mValueToIndex[val], 1); } int MoreCnt(const int& val) { return m_nums.size() - m_pTreeArr->Sum(mValueToIndex[val]); } vector<int> m_nums; protected: CTreeArr<int>* m_pTreeArr; unordered_map<int, int> mValueToIndex; }; class Solution { public: vector<int> resultArray(vector<int>& nums) { CTreeArrHlp hlp1(nums), hlp2(nums); hlp1.Add(nums[0]); hlp2.Add(nums[1]); for (int i = 2; i < nums.size(); i++) { const int i1 = hlp1.MoreCnt(nums[i]); const int i2 = hlp2.MoreCnt(nums[i]); if (i1 > i2) { hlp1.Add(nums[i]); } else if (i1 < i2) { hlp2.Add(nums[i]); } else { if (hlp1.m_nums.size() <= hlp2.m_nums.size()) { hlp1.Add(nums[i]); } else { hlp2.Add(nums[i]); } } } hlp1.m_nums.insert(hlp1.m_nums.end(), hlp2.m_nums.begin(), hlp2.m_nums.end()); return hlp1.m_nums; } };
使用封装的离散类
template class CTreeArr { public: CTreeArr(int iSize) :m_vData(iSize + 1) {
} void Add(int index, ELE value) { index++; while (index < m_vData.size()) { m_vData[index] += value; index += index & (-index); } } ELE Sum(int index) { index++; ELE ret = 0; while (index) { ret += m_vData[index]; index -= index & (-index); } return ret; } ELE Get(int index) { return Sum(index) - Sum(index - 1); }
private: vector m_vData; }; class CDiscretize //离散化 { public: CDiscretize(vector nums) { sort(nums.begin(), nums.end()); nums.erase(std::unique(nums.begin(), nums.end()), nums.end()); for (int i = 0; i < nums.size(); i++) { m_mValueToIndex[nums[i]] = i; } } int operator[](const int value)const { auto it = m_mValueToIndex.find(value); if (m_mValueToIndex.end() == it) { return -1; } return it->second; } int size()const { return m_mValueToIndex.size(); } protected: unordered_map<int, int> m_mValueToIndex; }; class CTreeArrHlp { public: CTreeArrHlp(vector nums):m_dis(nums),m_treeArr(m_dis.size()) { } void Add(const int& val) { m_nums.emplace_back(val); m_treeArr.Add(m_dis[val], 1); } int MoreCnt(const int& val) { return m_nums.size() - m_treeArr.Sum(m_dis[val]); } vector m_nums; protected: CDiscretize m_dis; CTreeArr m_treeArr; }; class Solution { public: vector resultArray(vector& nums) { CTreeArrHlp hlp1(nums), hlp2(nums); hlp1.Add(nums[0]); hlp2.Add(nums[1]); for (int i = 2; i < nums.size(); i++) { const int i1 = hlp1.MoreCnt(nums[i]); const int i2 = hlp2.MoreCnt(nums[i]); if (i1 > i2) { hlp1.Add(nums[i]); } else if (i1 < i2) { hlp2.Add(nums[i]); } else { if (hlp1.m_nums.size() <= hlp2.m_nums.size()) { hlp1.Add(nums[i]); } else { hlp2.Add(nums[i]); } } } hlp1.m_nums.insert(hlp1.m_nums.end(), hlp2.m_nums.begin(), hlp2.m_nums.end()); return hlp1.m_nums; } };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums = { 11,92,25,90 }; { Solution sln; ; auto res = sln.resultArray(nums); Assert({ 11,92,25,90 }, res); } }
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
如无特殊说明，本算法用**C++**实现。
