⭐ 题目日期：

华为 - 2024/11/2

🌳 题目描述：

给定一个数组只含 0 和 1，返回最小的 0, 1 交换次数，让所有的 1 都连续

示例 1:
输入：[1, 1, 0, 1, 1, 0, 0, 1]
输出：1
解释：只需将数组中的第三个数 0 和 最后一个数 1 交换位置，所有的 1 都连续排列

示例 2:
输入：[0, 0, 1]
输出：0
解释：数组中所有的 1 已经连续排列，不需要进行交换

🕵🏽 面试评估：

这道题主要考查定长滑动窗口，难点在于将问题模型转为滑动窗口算法来解题。

🧗 难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

从初始的杂乱状态到最终所有 1 连续排列，确定的是覆盖所有 1 的窗口长度(等于数组中 1 的个数)，不确定的是窗口的位置

窗口可能落在数组中的任何位置，因此我们需要从数组的开始滑动窗口至数组的末尾，沿途统计窗口内最少 0 的个数，也就是0 1 最少的交换的次数。

💻代码：

Java

public int minSwaps(int[] data) {
   int ones = 0;
   for (int num : data) {
       if (num == 1) {
           ones++;
       }
   }

   int minSwaps = Integer.MAX_VALUE;
   int zerosInWindow = 0;
   int left = 0;
   for (int right = 0; right < data.length; right++) {
       // 统计窗口内 0 的数量
       if (data[right] == 0) {
           zerosInWindow++;
       }

       // 当窗口大小达到 ones 时，开始更新最小交换次数
       if (right - left + 1 == ones) {
           minSwaps = Math.min(minSwaps, zerosInWindow);
           // 移动左边界，更新窗口内 0 的数量
           if (data[left] == 0) {
               zerosInWindow--;
           }
           left++;
       }
   }

   return minSwaps == Integer.MAX_VALUE ? 0 : minSwaps;
}

🚵🏻复杂度分析：

时间复杂度: O(n)，数组最多线性扫描两遍

空间复杂度: O(1)