本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给你一个数组 nums，我们可以将它按一个非负整数 k 进行轮调，这样可以使数组变为 [nums[k], nums[k + 1], … nums[nums.length - 1], nums[0], nums[1], …, nums[k-1]] 的形式。此后，任何值小于或等于其索引的项都可以记作一分。
例如，数组为 nums = [2,4,1,3,0]，我们按 k = 2 进行轮调后，它将变成 [1,3,0,2,4]。这将记为 3 分，因为 1 > 0 [不计分]、3 > 1 [不计分]、0 <= 2 [计 1 分]、2 <= 3 [计 1 分]，4 <= 4 [计 1 分]。
在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调下标 k 。如果有多个答案，返回满足条件的最小的下标 k 。
示例 1：
输入：nums = [2,3,1,4,0]
输出：3
解释：
下面列出了每个 k 的得分：
k = 0, nums = [2,3,1,4,0], score 2
k = 1, nums = [3,1,4,0,2], score 3
k = 2, nums = [1,4,0,2,3], score 3
k = 3, nums = [4,0,2,3,1], score 4
k = 4, nums = [0,2,3,1,4], score 3
所以我们应当选择 k = 3，得分最高。
示例 2：
输入：nums = [1,3,0,2,4]
输出：0
解释：
nums 无论怎么变化总是有 3 分。
所以我们将选择最小的 k，即 0。
提示：
1 <= nums.length <= 10^5
0 <= nums[i] < nums.length
分析
我可以将结果分为两部分，左边（i < k )得分，右边（i>k)得分。iSub是值减去当前索引,iSub小于等于0，则加分。我们以{1,5,2,4,3}为例。
对于左边
iSub=num[i]-i-(m_c-k)
| k取值 | 左边的值减当前索引 | 旧数据变化分数变化 | 新增加的数据分数变化 | 总分数 |
| 0 | {} | +0 | +0 | 0 |
| 1 | {- 3} | +0 | +1 | 1 |
| 2 | {-2,1} | +0 | +0 | 1 |
| 3 | {-1,2,- 2} | +0 | +1 | 2 |
| 4 | {0,3,-1,0} | +0 | +1 | 3 |
如果遍历所有旧值，那总时间复杂度会达到O(n*n)，超时。实际上我们值需要统计新iSub是1的值，也就是num[i]-i-(m_c-k) 等于1，也就是初始iSum 等于= 1 + m_c-k，这样总时间复杂度是O(1)。
对于右边
iSum = num[i] - i + k
| k取值 | 值减当前索引 | 旧数据变化分数变化 | 新增加的数据分数变化 | 总分数 |
| 4 | {3} | +0 | +0 | 0 |
| 3 | {4,2} | +0 | +0 | 0 |
| 2 | {2,3,1} | +0 | +0 | 0 |
| 1 | {5,1,2,0} | +1 | +0 | 1 |
| 0 | {1,4,0,1,-1} | +1 | +0 | 2 |
| k减少1，iSub也减少1 |
思路
mLeftSubToNum和mRightSubToNum记录初始nums[i]-i 。i>=k，记录在mRightSubToNum;否则记录子mLeftSubToNum。
核心代码
class Solution { public: int bestRotation(vector& nums) { m_c = nums.size(); //mLeftSubToNum和mRightSubToNum记录初始nums[i]-i 。i>=k，记录在mRightSubToNum;否则记录子mLeftSubToNum unordered_map<int, int> mLeftSubToNum, mRightSubToNum; m_vRet.resize(m_c);
vector<int> vLeft(m_c);//vLeft[i]记录初始i < k的分数 { int iPre = 0; for (int k = 1; k < m_c; k++) { //将k-1从右边移动到左边 const int iSub = nums[k - 1] - (k - 1); if (iSub - (m_c - k) <= 0) {//新增加的值得一分 iPre++; } iPre -= mLeftSubToNum[1 + m_c - k]; vLeft[k] = iPre; mLeftSubToNum[iSub]++; } } vector<int> vRight(m_c); { int iPre = 0; for (int k = m_c-1; k >= 0 ; k-- ) { const int iSub = nums[k] - k; if (iSub + k <= 0) { iPre++; } if (mRightSubToNum.count(-k)) { iPre += mRightSubToNum[-k]; } vRight[k] = iPre; mRightSubToNum[iSub]++; } } //m_vRet[k]记录的分值 for (int i = 0 ; i < m_c ;i++ ) { m_vRet[i] = vLeft[i] + vRight[i]; } //本题一定有答案，所以不用判断非法值 return std::max_element(m_vRet.begin(), m_vRet.end()) - m_vRet.begin(); } vector<int> m_vRet; int m_c;
};
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector nums = { 1,5,2,4,3 }; Solution sln; auto res = sln.bestRotation(nums); Assert(res, 4); Assert({ 2,2,1,2,3 }, sln.m_vRet); nums = { 2,3,1,4,0 }; res = sln.bestRotation(nums); Assert(res, 3); Assert({ 2,3,3,4,3 },sln.m_vRet ); nums = { 1,3,0,2,4 }; res = sln.bestRotation(nums); Assert(res, 0); Assert({ 3,3,3,3,3 }, sln.m_vRet);
//CConsole::Out(res);
}
2023年4月
旧版仅供参考
class Solution { public: int bestRotation(vector& nums) { std::unordered_map<int, int> mLeftSumNums; int iScore = 0; for (int i = 0; i < nums.size(); i++) { const int iSub = nums[i] - i; mLeftSumNums[iSub]++; if (iSub <= 0) { iScore++; } }
std::unordered_map<int, int> mRightSumNums; int iMaxScore = iScore; int iMaxIndex = 0; for (int i = 1; i < nums.size(); i++) { if (nums[i - 1] <= 0 ) { iScore--; } const int iSub = nums[i - 1] - (i - 1); mLeftSumNums[iSub]--; iScore -= mLeftSumNums[-(i-1)]; //右边，部分不再加分 iScore -= mRightSumNums[-(i-1)]; const int iRightSub = nums[i-1] - (nums.size() - 1) - i; mRightSumNums[iRightSub]++; if ( (nums[i-1] - ((int)nums.size() - 1)) <= 0) { iScore++; } if (iScore > iMaxScore) { iMaxScore = iScore; iMaxIndex = i; } } return iMaxIndex; }
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
