README.md

2340. Minimum Adjacent Swaps to Make a Valid Array

English Version

题目描述

You are given a 0-indexed integer array nums.

Swaps of adjacent elements are able to be performed on nums.

A valid array meets the following conditions:

• The largest element (any of the largest elements if there are multiple) is at the rightmost position in the array.
• The smallest element (any of the smallest elements if there are multiple) is at the leftmost position in the array.

Return the minimum swaps required to make nums a valid array.

 

Example 1:

Input: nums = [3,4,5,5,3,1]
Output: 6
Explanation: Perform the following swaps:
- Swap 1: Swap the 3rd and 4th elements, nums is then [3,4,5,3,5,1].
- Swap 2: Swap the 4th and 5th elements, nums is then [3,4,5,3,1,5].
- Swap 3: Swap the 3rd and 4th elements, nums is then [3,4,5,1,3,5].
- Swap 4: Swap the 2nd and 3rd elements, nums is then [3,4,1,5,3,5].
- Swap 5: Swap the 1st and 2nd elements, nums is then [3,1,4,5,3,5].
- Swap 6: Swap the 0th and 1st elements, nums is then [1,3,4,5,3,5].
It can be shown that 6 swaps is the minimum swaps required to make a valid array.

Example 2:

Input: nums = [9]
Output: 0
Explanation: The array is already valid, so we return 0.

 

Constraints:

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

解法

方法一：贪心 + 分类讨论

我们先找出数组中第一个最小值和最后一个最大值的位置，分别记为 $i$ 和 $j$。

如果 $i$ 和 $j$ 相等，说明数组已经是有效的，直接返回 $0$ 即可。

否则，我们判断 $i$ 是否在 $j$ 的左边，如果是，那么交换次数为 $i + n - 1 - j$；否则，交换次数为 $i + n - 2 - j$。

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

Python3

class Solution:
    def minimumSwaps(self, nums: List[int]) -> int:
        mi, mx = min(nums), max(nums)
        i, j = -1, -1
        for k, v in enumerate(nums):
            if v == mi and i == -1:
                i = k
            if v == mx:
                j = k
        if i == j:
            return 0
        n = len(nums)
        if i < j:
            return i + n - 1 - j
        return i + n - 2 - j

Java

class Solution {
    public int minimumSwaps(int[] nums) {
        int n = nums.length;
        int mi = min(nums), mx = max(nums);
        int i = -1, j = -1;
        for (int k = 0; k < n; ++k) {
            if (nums[k] == mi && i == -1) {
                i = k;
            }
            if (nums[k] == mx) {
                j = k;
            }
        }
        if (i == j) {
            return 0;
        }
        return i < j ? i + n - 1 - j : i + n - 2 - j;
    }

    private int max(int[] nums) {
        int v = 0;
        for (int x : nums) {
            v = Math.max(v, x);
        }
        return v;
    }

    private int min(int[] nums) {
        int v = nums[0];
        for (int x : nums) {
            v = Math.min(v, x);
        }
        return v;
    }
}

C++

class Solution {
public:
    int minimumSwaps(vector<int>& nums) {
        int n = nums.size();
        int mi = *min_element(nums.begin(), nums.end());
        int mx = *max_element(nums.begin(), nums.end());
        int i = -1, j = -1;
        for (int k = 0; k < n; ++k) {
            if (nums[k] == mi && i == -1) i = k;
            if (nums[k] == mx) j = k;
        }
        if (i == j) return 0;
        return i < j ? i + n - 1 - j : i + n - 2 - j;
    }
};

Go

func minimumSwaps(nums []int) int {
	mi, mx := nums[0], 0
	for _, v := range nums {
		mi = min(mi, v)
		mx = max(mx, v)
	}
	i, j := -1, -1
	for k, v := range nums {
		if v == mi && i == -1 {
			i = k
		}
		if v == mx {
			j = k
		}
	}
	if i == j {
		return 0
	}
	n := len(nums)
	if i < j {
		return i + n - 1 - j
	}
	return i + n - 2 - j
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

TypeScript

...