跳转至

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

题目描述

给定一个 下标从 0 开始 的整数数组 nums。

nums 上的 相邻 元素可以进行 交换。

一个 有效 的数组必须满足以下条件:

  • 最大的元素 (如果有多个，则为最大元素中的任何一个) 位于数组中最右边的位置。
  • 最小的元素 (如果有多个，则为最小的任何一个元素) 位于数组的最左侧。

返回使 nums 成为有效数组所需的最少交换次数。

 

示例 1:

输入: nums = [3,4,5,5,3,1]
输出: 6
解释: 进行以下交换:
- 交换 1:交换第 3 和第 4 个元素，然后 nums 是 [3,4,5,3,5,1].
- 交换 2:交换第 4 和第 5 个元素，然后 nums 是 [3,4,5,3,1,5].
- 交换 3:交换第 3 和第 4 个元素，然后 nums 是  [3,4,5,1,3,5].
- 交换 4:交换第 2 和第 3 个元素，然后 nums 是  [3,4,1,5,3,5].
- 交换 5:交换第 1 和第 2 个元素，然后 nums 是  [3,1,4,5,3,5].
- 交换 6:交换第 0 和第 1 个元素，然后 nums 是  [1,3,4,5,3,5].
可以证明，6 次交换是组成一个有效数组所需的最少交换次数。

示例 2:

输入: nums = [9]
输出: 0
解释: 该数组已经有效，因此返回 0。

 

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

解法

方法一：维护最值下标 + 分类讨论

我们可以用下标 $i$ 和 $j$ 分别记录数组 $\textit{nums}$ 第一个最小值和最后一个最大值的下标，遍历数组 $\textit{nums}$，更新 $i$ 和 $j$ 的值。

接下来，我们需要考虑交换的次数。

  • 如果 $i = j$，说明数组 $\textit{nums}$ 已经是有效数组，不需要交换，返回 $0$；
  • 如果 $i < j$，说明数组 $\textit{nums}$ 中最小值在最大值的左边，需要交换 $i + n - 1 - j$ 次，其中 $n$ 为数组 $\textit{nums}$ 的长度；
  • 如果 $i > j$，说明数组 $\textit{nums}$ 中最小值在最大值的右边，需要交换 $i + n - 1 - j - 1$ 次。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。

1
2
3
4
5
6
7
8
9
class Solution:
    def minimumSwaps(self, nums: List[int]) -> int:
        i = j = 0
        for k, v in enumerate(nums):
            if v < nums[i] or (v == nums[i] and k < i):
                i = k
            if v >= nums[j] or (v == nums[j] and k > j):
                j = k
        return 0 if i == j else i + len(nums) - 1 - j - (i > j)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minimumSwaps(int[] nums) {
        int n = nums.length;
        int i = 0, j = 0;
        for (int k = 0; k < n; ++k) {
            if (nums[k] < nums[i] || (nums[k] == nums[i] && k < i)) {
                i = k;
            }
            if (nums[k] > nums[j] || (nums[k] == nums[j] && k > j)) {
                j = k;
            }
        }
        if (i == j) {
            return 0;
        }
        return i + n - 1 - j - (i > j ? 1 : 0);
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func minimumSwaps(nums []int) int {
    var i, j int
    for k, v := range nums {
        if v < nums[i] || (v == nums[i] && k < i) {
            i = k
        }
        if v > nums[j] || (v == nums[j] && k > j) {
            j = k
        }
    }
    if i == j {
        return 0
    }
    if i < j {
        return i + len(nums) - 1 - j
    }
    return i + len(nums) - 2 - j
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function minimumSwaps(nums: number[]): number {
    let i = 0;
    let j = 0;
    const n = nums.length;
    for (let k = 0; k < n; ++k) {
        if (nums[k] < nums[i] || (nums[k] == nums[i] && k < i)) {
            i = k;
        }
        if (nums[k] > nums[j] || (nums[k] == nums[j] && k > j)) {
            j = k;
        }
    }
    return i == j ? 0 : i + n - 1 - j - (i > j ? 1 : 0);
}

评论