- 博客主页:音符犹如代码
- 系列专栏:算法练习
- 关注博主,后期持续更新系列文章
- 如果有错误感谢请大家批评指出,及时修改
- 感谢大家点赞👍收藏⭐评论✍
目录
思路
解题方法
时间复杂度
空间复杂度
Code
思路
- 首先通过循环计算前缀和
cnt
和前缀乘积和s
,用于后续计算。 - 然后遍历数组的每个位置
i
。 - 计算当前位置
i
周围可以直接利用的1
的数量,以及还需要的数量need
。 - 通过调整尝试找到满足需求的最小操作次数,并更新最终的最小操作次数
ans
。
解题方法
- 利用前缀和与前缀乘积和来快速计算部分和与乘积和。
- 通过循环和二分查找来找到满足需求的最小操作次数。
时间复杂度
- 主要的时间复杂度在于外层的遍历
n
次,以及内部的二分查找,总体时间复杂度为 O(nlogn)
空间复杂度
- 创建了两个额外的辅助数组
cnt
和s
,空间复杂度为 O(n)
Code
class Solution {public long minimumMoves(int[] nums, int k, int maxChanges) {int n = nums.length;int[] cnt = new int[n + 1];long[] s = new long[n + 1];for (int i = 1; i <= n; ++i) {cnt[i] = cnt[i - 1] + nums[i - 1];s[i] = s[i - 1] + i * nums[i - 1];}long ans = Long.MAX_VALUE;for (int i = 1; i <= n; ++i) {long t = 0;int need = k - nums[i - 1];for (int j = i - 1; j <= i + 1; j += 2) {if (need > 0 && 1 <= j && j <= n && nums[j - 1] == 1) {--need;++t;}}int c = Math.min(need, maxChanges);need -= c;t += c * 2;if (need <= 0) {ans = Math.min(ans, t);continue;}int l = 2, r = Math.max(i - 1, n - i);while (l <= r) {int mid = (l + r) >> 1;int l1 = Math.max(1, i - mid), r1 = Math.max(0, i - 2);int l2 = Math.min(n + 1, i + 2), r2 = Math.min(n, i + mid);int c1 = cnt[r1] - cnt[l1 - 1];int c2 = cnt[r2] - cnt[l2 - 1];if (c1 + c2 >= need) {long t1 = 1L * c1 * i - (s[r1] - s[l1 - 1]);long t2 = s[r2] - s[l2 - 1] - 1L * c2 * i;ans = Math.min(ans, t + t1 + t2);r = mid - 1;} else {l = mid + 1;}}}return ans;}
}