跳转至

3936. 将 0 移到末尾的最少交换次数

题目描述

给你一个整数数组 nums 。

在一步操作中，你可以选择任意两个 不同 的下标 i 和 j 并交换 nums[i] 和 nums[j] 。

返回将所有 0 移动到数组末尾所需的 最少 操作次数。

 

示例 1：

输入： nums = [0,1,0,3,12]

输出： 2

解释：

我们执行以下交换操作：

  • 交换 nums[0] 和 nums[3] ，得到 nums = [3, 1, 0, 0, 12] 。
  • 交换 nums[2] 和 nums[4] ，得到 nums = [3, 1, 12, 0, 0] 。

因此，答案是 2 。

示例 2：

输入： nums = [0,1,0,2]

输出： 1

解释：

我们执行以下交换操作：

  • 交换 nums[0] 和 nums[3] ，得到 nums = [2, 1, 0, 0] 。

因此，答案是 1 。

示例 3：

输入： nums = [1,2,0]

输出： 0

解释：

数组已经满足条件。因此，不需要任何交换操作。

 

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

解法

方法一：双指针

我们用两个指针 \(i\) 和 \(j\) 分别指向数组的开头和结尾。每次我们将 \(i\) 向右移动直到找到一个 0，将 \(j\) 向左移动直到找到一个非 0 的数。如果 \(i < j\)，我们就交换这两个数，并将答案加 1。重复这个过程直到 \(i \geq j\)。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minimumSwaps(self, nums: list[int]) -> int:
        ans = 0
        n = len(nums)
        i, j = 0, n - 1
        while i < j:
            while i < n and nums[i] != 0:
                i += 1
            while j and nums[j] == 0:
                j -= 1
            if i >= j:
                break
            ans += 1
            i += 1
            j -= 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minimumSwaps(int[] nums) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0, j = n - 1; i < j; ++i, --j) {
            while (i < n && nums[i] != 0) {
                ++i;
            }

            while (j > 0 && nums[j] == 0) {
                --j;
            }

            if (i >= j) {
                break;
            }

            ++ans;
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minimumSwaps(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0, j = n - 1; i < j; ++i, --j) {
            while (i < n && nums[i] != 0) {
                ++i;
            }

            while (j > 0 && nums[j] == 0) {
                --j;
            }

            if (i >= j) {
                break;
            }

            ++ans;
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minimumSwaps(nums []int) int {
    ans := 0
    n := len(nums)

    for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
        for i < n && nums[i] != 0 {
            i++
        }

        for j > 0 && nums[j] == 0 {
            j--
        }

        if i >= j {
            break
        }

        ans++
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function minimumSwaps(nums: number[]): number {
    let ans = 0;
    const n = nums.length;

    let i = 0;
    let j = n - 1;

    while (i < j) {
        while (i < n && nums[i] !== 0) {
            ++i;
        }

        while (j > 0 && nums[j] === 0) {
            --j;
        }

        if (i >= j) {
            break;
        }

        ++ans;
        ++i;
        --j;
    }

    return ans;
}

评论