Question

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

English Version

题目描述

给定一个 下标从 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$ 分别记录数组 nums 第一个最小值和最后一个最大值的下标，遍历数组 nums，更新 $i$ 和 $j$ 的值。

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

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

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

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)

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);
  }
}

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);
  }
};

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
}

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);
}