minimum-adjacent-swaps-for-k-consecutive-ones

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array, <code>nums</code>, and an integer <code>k</code>. <code>nums</code> comprises of only <code>0</code>&#39;s and <code>1</code>&#39;s. In one move, you can choose two adjacent indices and swap their values.

Return the minimum number of moves required so that <code>nums</code> has <code>k</code> consecutive <code>1</code>&#39;s.

&nbsp;
Example 1:

<pre>
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&#39;s.
</pre>

Example 2:

<pre>
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].
</pre>

Example 3:

<pre>
Input: nums = [1,1,0,1], k = 2
Output: 0
Explanation: nums already has 2 consecutive 1&#39;s.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>nums[i]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= k &lt;= sum(nums)</code></li>
</ul>

minMoves

Minimum Adjacent Swaps for K Consecutive Ones

Minimum Swaps to Group All 1's Together

minimum-swaps-to-group-all-1s-together

最少交换次数来组合所有的 1

Minimum Number of Operations to Make Array Continuous

minimum-number-of-operations-to-make-array-continuous

使数组连续的最少操作数

Minimum Adjacent Swaps to Make a Valid Array

minimum-adjacent-swaps-to-make-a-valid-array

生成有效数组的最少交换次数

Greedy

Array

Prefix Sum

Sliding Window

给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> 。 <code>nums</code> 仅包含 <code>0</code> 和 <code>1</code> 。每一次移动，你可以选择 相邻 两个数字并将它们交换。

请你返回使 <code>nums</code> 中包含 <code>k</code> 个 连续 <code>1</code> 的 最少 交换次数。

 

示例 1：

<pre>输入：nums = [1,0,0,1,0,1], k = 2
输出：1
解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。
</pre>

示例 2：

<pre>输入：nums = [1,0,0,0,0,0,1,1], k = 3
输出：5
解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。
</pre>

示例 3：

<pre>输入：nums = [1,1,0,1], k = 2
输出：0
解释：nums 已经有连续 2 个 1 了。
</pre>

 

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>nums[i]</code> 要么是 <code>0</code> ，要么是 <code>1</code> 。</li>
	<li><code>1 &lt;= k &lt;= sum(nums)</code></li>
</ul>