【树状数组】2659. 将数组清空

本文涉及知识点

树状数组

LeetCode2659. 将数组清空

给你一个包含若干互不相同整数的数组 nums ，你需要执行以下操作直到数组为空：
如果数组中第一个元素是当前数组中的最小值，则删除它。
否则，将第一个元素移动到数组的末尾。
请你返回需要多少个操作使 nums 为空。
示例 1：
输入：nums = [3,4,-1]
输出：5
Operation Array
1 [4, -1, 3]
2 [-1, 3, 4]
3 [3, 4]
4 [4]
5 []

示例 2：
输入：nums = [1,2,4,3]
输出：5
Operation Array
1 [2, 4, 3]
2 [4, 3]
3 [3, 4]
4 [4]
5 []
示例 3：
输入：nums = [1,2,3]
输出：3
Operation Array
1 [2, 3]
2 [3]
3 []
提示：
1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums 中的元素互不相同。

树状数组

indexs记录下标，nums[indexs[i]]升序。
n = nums.length
树状数组treeArr[i]表示nums[i]没有删除，没有删除为1，删除为0。初始全部为1。
删除的的操作次数：n
所以只需要记录移动的操作次数：
nums[indexs[0]] 需要移动：indexs[0]次
nums[indexs[i]],i>0 需要移动的次数：
x = abs(treeArr.Sum(indexs[i])-treeArr.Sum(indexs[i-1]))
$\begin{cases} x-1 && indexs[i-1] < indexs[i] \\ n-i - (x+1) &&other \\ \end{cases}$

代码

核心代码

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)//[0...index]之和{index++;ELE ret = 0;while (index){ret += m_vData[index];index -= index & (-index);}return ret;}ELE Sum() { return Sum(m_vData.size() - 2);	}ELE Get(int index){return Sum(index) - Sum(index - 1);}
private:vector<ELE> m_vData;
};class Solution {
public:long long countOperationsToEmptyArray(vector<int>& nums) {const int N = nums.size();vector<int> indexs(N);iota(indexs.begin(), indexs.end(), 0);sort(indexs.begin(), indexs.end(), [&](int i1, int i2) {return nums[i1] < nums[i2]; });long long ret = indexs[0];CTreeArr<int> treeArr(N);for (int i = 0; i < N; i++) {if (i == indexs[0]) { continue; }treeArr.Add(i, 1);}for (int i = 1; i < N; i++) {int i1 = treeArr.Sum(indexs[i - 1]);int i2 = treeArr.Sum(indexs[i]);int i3 = abs(i1 - i2);if (indexs[i - 1] < indexs[i]) {ret += (i3 - 1);}else {ret += (N - i - (i3+1));}treeArr.Add(indexs[i], -1);}return ret + N;}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<int> nums;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){nums = { 3, 4, -1 };auto res = Solution().countOperationsToEmptyArray(nums);AssertEx(5LL, res);}TEST_METHOD(TestMethod01){nums = { 1,2,4,3 };auto res = Solution().countOperationsToEmptyArray(nums);AssertEx(5LL, res);}TEST_METHOD(TestMethod02){nums = { 1,2,3 };auto res = Solution().countOperationsToEmptyArray(nums);AssertEx(3LL, res);}TEST_METHOD(TestMethod03){nums = { -15, -19, 5 };auto res = Solution().countOperationsToEmptyArray(nums);AssertEx(5LL, res);}TEST_METHOD(TestMethod04){nums = { 2,1 };auto res = Solution().countOperationsToEmptyArray(nums);AssertEx(3LL, res);}};
}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛