Medium

题目描述

给你一个由不同整数组成的数组 nums。

在一次操作中，你可以交换数组中任意两个相邻的元素。

如果数组的一种排列中相邻元素的奇偶性交替出现，即每对相邻元素都由一个偶数和一个奇数组成，则该排列被认为是有效的。

返回将 nums 转换为任意有效排列所需的最小相邻交换次数。

如果无法重新排列 nums 使得没有两个相邻元素具有相同的奇偶性，则返回 -1。

示例 1：

输入：nums = [2,4,6,5,7]
输出：3
解释：
交换 5 和 6，数组变为 [2,4,5,6,7]
交换 5 和 4，数组变为 [2,5,4,6,7]  
交换 6 和 7，数组变为 [2,5,4,7,6]。数组现在是有效排列。因此答案是 3。

示例 2：

输入：nums = [2,4,5,7]
输出：1
解释：
交换 4 和 5，数组变为 [2,5,4,7]，这是一个有效排列。因此答案是 1。

示例 3：

输入：nums = [1,2,3]
输出：0
解释：
数组已经是有效排列。因此不需要任何操作。

示例 4：

输入：nums = [4,5,6,8]
输出：-1
解释：
不可能有有效排列。因此答案是 -1。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums 中所有元素都不相同

解题思路

这道题要求通过相邻交换使数组的奇偶性交替排列。我们需要分析两种可能的目标模式：以偶数开头或以奇数开头。

核心思路：

  1. 可行性检查：首先统计偶数和奇数的个数。如果它们的个数差值大于1，则无法形成交替排列，返回-1。

  2. 模式分析：

    • 如果数组长度为奇数，只能选择数量较多的那种数字作为开头
    • 如果数组长度为偶数，两种模式都可能，需要都尝试并取最小值

  3. 贪心策略：对于确定的目标模式，我们需要将当前的偶数/奇数移动到目标位置。关键观察是，通过相邻交换，将一个元素从位置i移动到位置j的最小交换次数就是|i-j|。

  4. 计算交换次数：

    • 收集所有偶数的当前位置和目标位置
    • 收集所有奇数的当前位置和目标位置
    • 分别计算移动成本并求和

算法步骤：

  • 统计偶数和奇数个数，判断可行性
  • 根据数组长度确定需要尝试的模式
  • 对每种模式，计算偶数和奇数的移动成本
  • 返回最小成本

代码实现

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int n = nums.size();
        int evenCnt = 0, oddCnt = 0;
        
        for (int num : nums) {
            if (num % 2 == 0) evenCnt++;
            else oddCnt++;
        }
        
        if (abs(evenCnt - oddCnt) > 1) return -1;
        
        auto calculateCost = [&](bool evenFirst) -> int {
            vector<int> evenPos, oddPos;
            vector<int> evenTarget, oddTarget;
            
            for (int i = 0; i < n; i++) {
                if (nums[i] % 2 == 0) {
                    evenPos.push_back(i);
                } else {
                    oddPos.push_back(i);
                }
            }
            
            for (int i = 0; i < n; i++) {
                if ((i % 2 == 0) == evenFirst) {
                    evenTarget.push_back(i);
                } else {
                    oddTarget.push_back(i);
                }
            }
            
            int cost = 0;
            for (int i = 0; i < evenPos.size(); i++) {
                cost += abs(evenPos[i] - evenTarget[i]);
            }
            for (int i = 0; i < oddPos.size(); i++) {
                cost += abs(oddPos[i] - oddTarget[i]);
            }
            
            return cost;
        };
        
        if (n % 2 == 1) {
            return calculateCost(evenCnt > oddCnt);
        } else {
            return min(calculateCost(true), calculateCost(false));
        }
    }
};

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        even_cnt = sum(1 for num in nums if num % 2 == 0)
        odd_cnt = n - even_cnt
        
        if abs(even_cnt - odd_cnt) > 1:
            return -1
        
        def calculate_cost(even_first):
            even_pos = [i for i, num in enumerate(nums) if num % 2 == 0]
            odd_pos = [i for i, num in enumerate(nums) if num % 2 == 1]
            
            even_target = [i for i in range(n) if (i % 2 == 0) == even_first]
            odd_target = [i for i in range(n) if (i % 2 == 0) != even_first]
            
            cost = 0
            for i in range(len(even_pos)):
                cost += abs(even_pos[i] - even_target[i])
            for i in range(len(odd_pos)):
                cost += abs(odd_pos[i] - odd_target[i])
            
            return cost
        
        if n % 2 == 1:
            return calculate_cost(even_cnt > odd_cnt)
        else:
            return min(calculate_cost(True), calculate_cost(False))

public class Solution {
    public int MinSwaps(int[] nums) {
        int n = nums.Length;
        int evenCnt = 0, oddCnt = 0;
        
        foreach (int num in nums) {
            if (num % 2 == 0) evenCnt++;
            else oddCnt++;
        }
        
        if (Math.Abs(evenCnt - oddCnt) > 1) return -1;
        
        int CalculateCost(bool evenFirst) {
            var evenPos = new List<int>();
            var oddPos = new List<int>();
            var evenTarget = new List<int>();
            var oddTarget = new List<int>();
            
            for (int i = 0; i < n; i++) {
                if (nums[i] % 2 == 0) {
                    evenPos.Add(i);
                } else {
                    oddPos.Add(i);
                }
            }
            
            for (int i = 0; i < n; i++) {
                if ((i % 2 == 0) == evenFirst) {
                    evenTarget.Add(i);
                } else {
                    oddTarget.Add(i);
                }
            }
            
            int cost = 0;
            for (int i = 0; i < evenPos.Count; i++) {
                cost += Math.Abs(evenPos[i] - evenTarget[i]);
            }
            for (int i = 0; i < oddPos.Count; i++) {
                cost += Math.Abs(oddPos[i] - oddTarget[i]);
            }
            
            return cost;
        }
        
        if (n % 2 == 1) {
            return CalculateCost(evenCnt > oddCnt);
        } else {
            return Math.Min(CalculateCost(true), CalculateCost(false));
        }
    }
}

var minSwaps = function(nums) {
    const n = nums.length;
    const evens = [];
    const odds = [];
    
    for (let i = 0; i < n; i++) {
        if (nums[i] % 2 === 0) {
            evens.push(i);
        } else {
            odds.push(i);
        }
    }
    
    if (Math.abs(evens.length - odds.length) > 1) {
        return -1;
    }
    
    function countSwaps(firstType, firstIndices, secondIndices) {
        let swaps = 0;
        let arr = [...nums];
        
        for (let i = 0; i < n; i++) {
            const needEven = (firstType === 'even' && i % 2 === 0) || (firstType === 'odd' && i % 2 === 1);
            
            if ((arr[i] % 2 === 0) !== needEven) {
                let j = i + 1;
                while (j < n && (arr[j] % 2 === 0) === (arr[i] % 2 === 0)) {
                    j++;
                }
                
                while (j > i) {
                    [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
                    swaps++;
                    j--;
                }
            }
        }
        
        return swaps;
    }
    
    let result = Infinity;
    
    if (evens.length >= odds.length) {
        result = Math.min(result, countSwaps('even', evens, odds));
    }
    
    if (odds.length >= evens.length) {
        result = Math.min(result, countSwaps('odd', odds, evens));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：遍历数组统计奇偶数个数需要O(n)，计算每种模式的成本也需要O(n)，最多计算2种模式，总体为O(n)
  • 空间复杂度：需要存储位置数组，最坏情况下需要O(n)的额外空间