You are given an integer array, nums
, and an integer k
. nums
comprises of only 0
‘s and 1
‘s. In one move, you can choose two adjacent indices and swap their values.
Return the minimum number of moves required so that nums
has k
consecutive 1
‘s.
Example 1:
Input: nums = [1,0,0,1,0,1], k = 2 Output: 1 Explanation: In 1 move, nums could be [1,0,0,0,1,1] and have 2 consecutive 1's.
Example 2:
Input: nums = [1,0,0,0,0,0,1,1], k = 3 Output: 5 Explanation: In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,1,1,1].
Example 3:
Input: nums = [1,1,0,1], k = 2 Output: 0 Explanation: nums already has 2 consecutive 1's.
Constraints:
1 <= nums.length <= 105
nums[i]
is0
or1
.1 <= k <= sum(nums)
Solution: Prefix Sum + Sliding Window
Time complexity: O(n)
Space complexity: O(n)
We only care positions of 1s, we can move one element from position x to y (assuming x + 1 ~ y are all zeros) in y – x steps. e.g. [0 0 1 0 0 0 1] => [0 0 0 0 0 1 1], move first 1 at position 2 to position 5, cost is 5 – 2 = 3.
Given a size k window of indices of ones, the optimal solution it to use the median number as center. We can compute the cost to form consecutive numbers:
e.g. [1 4 7 9 10] => [5 6 7 8 9] cost = (5 – 1) + (6 – 4) + (9 – 8) + (10 – 9) = 8
However, naive solution takes O(n*k) => TLE.
We can use prefix sum to compute the cost of a window in O(1) to reduce time complexity to O(n)
First, in order to use sliding window, we change the target of every number in the window to the median number.
e.g. [1 4 7 9 10] => [7 7 7 7 7] cost = (7 – 1) + (7 – 4) + (7 – 7) + (9 – 7) + (10 – 7) = (9 + 10) – (1 + 4) = right – left.
[5 6 7 8 9] => [7 7 7 7 7] takes extra 2 + 1 + 1 + 2 = 6 steps = (k / 2) * ((k + 1) / 2), these extra steps should be deducted from the final answer.
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: int minMoves(vector<int>& nums, int k) { vector<long> s(1); for (int i = 0; i < nums.size(); ++i) if (nums[i]) s.push_back(s.back() + i); const int n = s.size(); long ans = 1e10; const int m1 = k / 2, m2 = (k + 1) / 2; for (int i = 0; i + k < n; ++i) { const long right = s[i + k] - s[i + m1]; const long left = s[i + m2] - s[i]; ans = min(ans, right - left); } return ans - m1 * m2; } }; |
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution: def minMoves(self, nums: List[int], k: int) -> int: ans = 1e10 s = [0] for i, v in enumerate(nums): if v: s.append(s[-1] + i) n = len(s) m1 = k // 2 m2 = (k + 1) // 2 for i in range(n - k): right = s[i + k] - s[i + m1] left = s[i + m2] - s[i] ans = min(ans, right - left) return ans - m1 * m2 |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment