class Solution {
public:
int minimumSwaps(vector<int>& nums) {
}
};
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 <= 1051 <= nums[i] <= 105原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 53.9 MB, 提交时间: 2023-10-17 11:34:06
class Solution {
public int minimumSwaps(int[] nums) {
int min = 0;
int max = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[min]) min = i;
else if (nums[i] >= nums[max]) max = i ;
}
return (min - 0) + (nums.length - 1 - max) - (min > max ? 1 : 0 );
}
}
javascript 解法, 执行用时: 80 ms, 内存消耗: 47.9 MB, 提交时间: 2023-10-17 11:33:37
/**
* @param {number[]} nums
* @return {number}
*/
var minimumSwaps = function(nums) {
let min_i = 0, max_i = 0, c = 0;
for(let i = 0; i < nums.length; i++){
if(nums[min_i] > nums[i]){
min_i = i; // 最左边的最小值
}
if(nums[max_i] <= nums[i]){
max_i = i; // 最右边的最大值
}
}
if(max_i < min_i) c--;
return c + nums.length - 1 - max_i + min_i;
};
cpp 解法, 执行用时: 68 ms, 内存消耗: 49.1 MB, 提交时间: 2023-10-17 11:31:50
class Solution {
public:
int minimumSwaps(vector<int>& nums) {
if (nums.size() == 1) return 0;
int iMax, iMin;
int numMax = INT_MIN, numMin = INT_MAX;
//找最右边的最大值和最左边的最小值位置
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] < numMin) numMin = nums[i];
if (nums[i] >= numMax) {
numMax = nums[i];
iMax = i;
}
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == numMin) {
iMin = i;
break;
}
}
return iMin + nums.size() -1 - iMax + (iMin > iMax ? -1: 0 );
}
};
golang 解法, 执行用时: 56 ms, 内存消耗: 8.3 MB, 提交时间: 2023-10-17 11:31:30
func minimumSwaps(nums []int) int {
min, max:= 0, 0
for i:=0;i< len(nums);i++{
if nums[i] < nums[min]{
min = i
}
if nums[i] >= nums[max]{
max = i
}
}
ans:= min+len(nums)-1-max
if max < min{
ans--
}
return ans
}
python3 解法, 执行用时: 424 ms, 内存消耗: 29.4 MB, 提交时间: 2023-10-17 11:30:15
class Solution:
def minimumSwaps(self, nums: List[int]) -> int:
minv, maxv = min(nums), max(nums) # 最大最小值
minid, maxid = -1, -1 # 最大最小值索引
n = len(nums)
for i in range(n):
if nums[i] == minv:
if minid == -1:
minid = i
if nums[i] == maxv:
maxid = i
ans = minid - maxid + n - 1
return ans if minid <= maxid else ans - 1