题解 | #小红的有序数组#

小红的有序数组

https://www.nowcoder.com/practice/d4ee2b59f3564cfcac9a66161bca5a5c

题目链接

小红的有序数组

题目描述

给定一个长度为 $n$ 的排列（ $1$ 到 $n$ 的数字不重不漏）。

每次操作可以选择两个奇偶性相同的数进行交换。

求最少需要多少次操作才能使得数组变成有序的（即 [1, 2, 3, ..., n]）。如果无法变为有序，输出 -1。

解题思路

这个问题的核心在于理解交换操作的限制：只有奇偶性相同的数才能交换。

1. 可行性分析 (无解情况)

这个限制意味着，奇数集合和偶数集合是完全隔离的。一个奇数永远只能和另一个奇数交换，它永远无法移动到一个偶数所在的位置。

在最终有序的数组 [1, 2, ..., n] 中，所有奇数都在奇数位置上（第1, 3, 5...位），所有偶数都在偶数位置上（第2, 4, 6...位）。

因此，一个数若要能被正确归位，它当前所在位置的奇偶性，必须和它最终目标位置的奇偶性相同。而一个数 $k$ 的最终目标位置就是第 $k$ 位。所以，数 $k$ 所在位置的奇偶性必须和 $k$ 的奇偶性相同。

这就导出了一个强力的无解条件：如果初始数组中，存在任何一个数 a[i]，它的值的奇偶性与它所在位置 i+1 的奇偶性不同，那么这个数就永远无法被归位，整个数组也就不可能排好序。

所以，我们可以先遍历一遍数组，检查 a[i] % 2 != (i+1) % 2 是否成立。一旦成立，就输出 -1。

2. 最小交换次数

如果数组通过了可行性检查，说明所有奇数都在奇数位，所有偶数都在偶数位。问题就被分解成了两个完全独立的子问题：

子问题A: 对所有在奇数位的数进行排序。
子问题B: 对所有在偶数位的数进行排序。

总的最小交换次数等于这两个子问题所需的最小交换次数之和。

每个子问题都是一个经典的排列排序问题：“给定一个排列，求恢复有序所需的最少交换次数”。这个问题的经典结论是：最小交换次数 = 元素数量 - 置换环的个数。

一个置换环是指，元素 $v_1$ 在 $v_2$ 的正确位置上， $v_2$ 在 $v_3$ 的正确位置上，...，最终 $v_k$ 在 $v_1$ 的正确位置上，形成一个闭环。我们需要 k-1 次交换来解开一个长度为 $k$ 的环。

3. 算法步骤

可行性检查：遍历数组，若 a[i] % 2 != (i+1) % 2，则输出 -1 并结束。
分离子问题：创建两个新数组，一个存所有奇数位的数 (odds_arr)，另一个存所有偶数位的数 (evens_arr)。
计算交换次数：
- 对 odds_arr，计算将其排成 [1, 3, 5, ...] 所需的交换次数。这通过计算置换环的个数 C_odd 来实现，次数为 len(odds_arr) - C_odd。
- 对 evens_arr，同理计算将其排成 [2, 4, 6, ...] 所需的交换次数，为 len(evens_arr) - C_even。
汇总：将两个子问题的交换次数相加，即为最终答案。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

int count_swaps(const vector<int>& current, const vector<int>& sorted) {
    if (current.empty()) {
        return 0;
    }
    int n = current.size();
    map<int, int> val_to_idx;
    for (int i = 0; i < n; ++i) {
        val_to_idx[current[i]] = i;
    }

    vector<bool> visited(n, false);
    int cycles = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            cycles++;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = val_to_idx[sorted[j]];
            }
        }
    }
    return n - cycles;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> odds_arr, evens_arr;
    
    bool possible = true;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] % 2 != (i + 1) % 2) {
            possible = false;
        }
        if ((i + 1) % 2 != 0) {
            odds_arr.push_back(a[i]);
        } else {
            evens_arr.push_back(a[i]);
        }
    }

    if (!possible) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> target_odds, target_evens;
    for (int i = 1; i <= n; ++i) {
        if (i % 2 != 0) {
            target_odds.push_back(i);
        } else {
            target_evens.push_back(i);
        }
    }

    int odd_swaps = count_swaps(odds_arr, target_odds);
    int even_swaps = count_swaps(evens_arr, target_evens);

    cout << odd_swaps + even_swaps << endl;

    return 0;
}

import java.util.*;

public class Main {

    private static int countSwaps(List<Integer> current, List<Integer> sorted) {
        if (current.isEmpty()) {
            return 0;
        }
        int n = current.size();
        Map<Integer, Integer> valToIdx = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valToIdx.put(current.get(i), i);
        }

        boolean[] visited = new boolean[n];
        int cycles = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                cycles++;
                int j = i;
                while (!visited[j]) {
                    visited[j] = true;
                    j = valToIdx.get(sorted.get(j));
                }
            }
        }
        return n - cycles;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        List<Integer> oddsArr = new ArrayList<>();
        List<Integer> evensArr = new ArrayList<>();

        boolean possible = true;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            if (a[i] % 2 != (i + 1) % 2) {
                possible = false;
            }
            if ((i + 1) % 2 != 0) {
                oddsArr.add(a[i]);
            } else {
                evensArr.add(a[i]);
            }
        }

        if (!possible) {
            System.out.println(-1);
            return;
        }

        List<Integer> targetOdds = new ArrayList<>();
        List<Integer> targetEvens = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 2 != 0) {
                targetOdds.add(i);
            } else {
                targetEvens.add(i);
            }
        }

        int oddSwaps = countSwaps(oddsArr, targetOdds);
        int evenSwaps = countSwaps(evensArr, targetEvens);

        System.out.println(oddSwaps + evenSwaps);
    }
}

import sys

def count_swaps(current, sorted_arr):
    if not current:
        return 0
    n = len(current)
    val_to_idx = {val: i for i, val in enumerate(current)}
    
    visited = [False] * n
    cycles = 0
    
    for i in range(n):
        if not visited[i]:
            cycles += 1
            j = i
            while not visited[j]:
                visited[j] = True
                j = val_to_idx[sorted_arr[j]]
                
    return n - cycles

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    
    odds_arr = []
    evens_arr = []
    possible = True
    
    for i in range(n):
        if a[i] % 2 != (i + 1) % 2:
            possible = False
        
        if (i + 1) % 2 != 0:
            odds_arr.append(a[i])
        else:
            evens_arr.append(a[i])
            
    if not possible:
        print(-1)
        return
        
    target_odds = [i for i in range(1, n + 1) if i % 2 != 0]
    target_evens = [i for i in range(1, n + 1) if i % 2 == 0]
    
    odd_swaps = count_swaps(odds_arr, target_odds)
    even_swaps = count_swaps(evens_arr, target_evens)
    
    print(odd_swaps + even_swaps)

solve()

算法及复杂度

算法: 排列的置换环分解
时间复杂度: $\mathcal{O}(n)$ 。可行性检查和数组分离需要 $\mathcal{O}(n)$ 。计算环的个数时，每个元素仅被访问一次，所以也是 $\mathcal{O}(n)$ 。
空间复杂度: $\mathcal{O}(n)$ 。需要额外的空间来存储分离出的奇偶数组、位置映射表和访问标记数组。