nums

nums[left]和nums[r]都是1,且nums[left,r]共有k个1。

r。

先移m0移动m1需要m0-left,移动m1,需要m1-(left1)共需要m0m1-left2-1。

先移m1移动m0需要m1-left,移动m0,需要m0-(left1)共需要m0m1-left2-1。

公式:如果有n个数左移则交换次数为这些数距离left的和-n*(n-1)/2。

如果m1左移更划算那么m0左移也更划算

m0相比与m1左移消耗更少右移消耗更多。

显然左移更划算。

右移类似。

代码解释

vOneIndex依次记录了nums[i]等于1的索引。

m是[left,r]中第一个右移划算的0。

[left,m)中的0

左移[m,end)中的0右移。

由于nums[end]是1所以[m,end]中的0就是[m,end)中的0。

v0Dis[m]

iRight0Num是[m,r)中的0全部从r移动到0。

v0Dis[r]

v0Dis[m

][m,r)中的0全部移动到0。

两者相减就是[m,r)的0全部移到r需要的次数。

时间复杂度

O(n)。

枚举i,时间复杂度O(n)枚举m时间复杂度O(n)。

注意m不是从头开始所以枚举m的总时间复杂度是O(n)而不是每个i都是O(n)。

核心代码

v0Dis.emplace_back(llAddv0Dis.back());

vector

v0Num.emplace_back(v0Num.back()

(0n));

//[m,end)中的0右移由于nums[end]是1所以[m,end]中的0就是[m,end)中的0

const

拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

https://edu.csdn.net/lecturer/6176

相关下载

https://download.csdn.net/download/he_zhidan/88348653

鄙人想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。

墨家名称的来源有所得以墨记之。

如果程序是一条龙那算法就是他的是睛

测试环境