题目
给你一个数组 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;
}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;
}};扩展阅读
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
鄙人想对大家说的话 |
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
墨家名称的来源：有所得以墨记之。 |
如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
