Question

1703. Minimum Adjacent Swaps for K Consecutive Ones

中文文档

Description

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] is 0 or 1.
• 1 <= k <= sum(nums)

Solutions

Solution 1: Prefix Sum + Median Enumeration

We can store the indices of $1$s in the array $nums$ into an array $arr$. Next, we preprocess the prefix sum array $s$ of the array $arr$, where $s[i]$ represents the sum of the first $i$ elements in the array $arr$.

For a subarray of length $k$, the number of elements on the left (including the median) is $x=\frac{k+1}{2}$, and the number of elements on the right is $y=k-x$.

We enumerate the index $i$ of the median, where $x-1\leq i\leq len(arr)-y$. The prefix sum of the left array is $ls=s[i+1]-s[i+1-x]$, and the prefix sum of the right array is $rs=s[i+1+y]-s[i+1]$. The current median index in $nums$ is $j=arr[i]$. The number of operations required to move the left $x$ elements to $[j-x+1,..j]$ is $a=(j+j-x+1)\times\frac{x}{2}-ls$, and the number of operations required to move the right $y$ elements to $[j+1,..j+y]$ is $b=rs-(j+1+j+y)\times\frac{y}{2}$. The total number of operations is $a+b$, and we take the minimum of all total operation counts.

The time complexity is $O(n)$, and the space complexity is $O(m)$. Here, $n$ and $m$ are the length of the array $nums$ and the number of $1$s in the array $nums$, respectively.

class Solution:
  def minMoves(self, nums: List[int], k: int) -> int:
    arr = [i for i, x in enumerate(nums) if x]
    s = list(accumulate(arr, initial=0))
    ans = inf
    x = (k + 1) // 2
    y = k - x
    for i in range(x - 1, len(arr) - y):
      j = arr[i]
      ls = s[i + 1] - s[i + 1 - x]
      rs = s[i + 1 + y] - s[i + 1]
      a = (j + j - x + 1) * x // 2 - ls
      b = rs - (j + 1 + j + y) * y // 2
      ans = min(ans, a + b)
    return ans

class Solution {
  public int minMoves(int[] nums, int k) {
    List<Integer> arr = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      if (nums[i] != 0) {
        arr.add(i);
      }
    }
    int m = arr.size();
    int[] s = new int[m + 1];
    for (int i = 0; i < m; ++i) {
      s[i + 1] = s[i] + arr.get(i);
    }
    long ans = 1 << 60;
    int x = (k + 1) / 2;
    int y = k - x;
    for (int i = x - 1; i < m - y; ++i) {
      int j = arr.get(i);
      int ls = s[i + 1] - s[i + 1 - x];
      int rs = s[i + 1 + y] - s[i + 1];
      long a = (j + j - x + 1L) * x / 2 - ls;
      long b = rs - (j + 1L + j + y) * y / 2;
      ans = Math.min(ans, a + b);
    }
    return (int) ans;
  }
}

class Solution {
public:
  int minMoves(vector<int>& nums, int k) {
    vector<int> arr;
    for (int i = 0; i < nums.size(); ++i) {
      if (nums[i]) {
        arr.push_back(i);
      }
    }
    int m = arr.size();
    long s[m + 1];
    s[0] = 1;
    for (int i = 0; i < m; ++i) {
      s[i + 1] = s[i] + arr[i];
    }
    long ans = 1L << 60;
    int x = (k + 1) / 2;
    int y = k - x;
    for (int i = x - 1; i < m - y; ++i) {
      int j = arr[i];
      int ls = s[i + 1] - s[i + 1 - x];
      int rs = s[i + 1 + y] - s[i + 1];
      long a = (j + j - x + 1L) * x / 2 - ls;
      long b = rs - (j + 1L + j + y) * y / 2;
      ans = min(ans, a + b);
    }
    return ans;
  }
};

func minMoves(nums []int, k int) int {
  arr := []int{}
  for i, x := range nums {
    if x != 0 {
      arr = append(arr, i)
    }
  }
  s := make([]int, len(arr)+1)
  for i, x := range arr {
    s[i+1] = s[i] + x
  }
  ans := 1 << 60
  x := (k + 1) / 2
  y := k - x
  for i := x - 1; i < len(arr)-y; i++ {
    j := arr[i]
    ls := s[i+1] - s[i+1-x]
    rs := s[i+1+y] - s[i+1]
    a := (j+j-x+1)*x/2 - ls
    b := rs - (j+1+j+y)*y/2
    ans = min(ans, a+b)
  }
  return ans
}