小米面试题-最小交换次数（只能交换相邻位置的元素）

Categories:

题目描述
思路分析
1. 解法一：归并排序统计逆序对（推荐）
2. 解法二：树状数组 + 离散化
相似题目

题目描述

✅ 小米面试题-最小交换次数（只能交换相邻位置的元素）

给定一个无序整数数组 nums，你只能交换相邻的元素，求将数组排序成递增顺序所需的最小交换次数。

思路分析

解法一：归并排序统计逆序对（推荐）

核心思路：

只能交换相邻元素时，最小交换次数等于数组的逆序对数量。

使用归并排序，在合并阶段统计跨区间逆序对。

每次当右侧元素小于左侧元素时，说明左侧剩余元素均与该右侧元素构成逆序对。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，归并辅助数组。

class Solution {
    public long minSwaps(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0L;
        }

        return mergeSort(nums, 0, nums.length - 1);
    }

    private long mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0L;
        }

        int mid = left + (right - left) / 2;
        long count = 0L;

        count += mergeSort(nums, left, mid);
        count += mergeSort(nums, mid + 1, right);

        int[] tmp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
                count += mid - i + 1;
            }
        }

        while (i <= mid) {
            tmp[k++] = nums[i++];
        }

        while (j <= right) {
            tmp[k++] = nums[j++];
        }

        System.arraycopy(tmp, 0, nums, left, tmp.length);
        return count;
    }
}

func minSwaps(nums []int) int64 {
	if len(nums) <= 1 {
		return 0
	}

	return mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, left int, right int) int64 {
	if left >= right {
		return 0
	}

	mid := left + (right-left)/2
	count := int64(0)

	count += mergeSort(nums, left, mid)
	count += mergeSort(nums, mid+1, right)

	tmp := make([]int, right-left+1)
	i, j, k := left, mid+1, 0

	for i <= mid && j <= right {
		if nums[i] <= nums[j] {
			tmp[k] = nums[i]
			i++
		} else {
			tmp[k] = nums[j]
			j++
			count += int64(mid - i + 1)
		}
		k++
	}

	for i <= mid {
		tmp[k] = nums[i]
		i++
		k++
	}

	for j <= right {
		tmp[k] = nums[j]
		j++
		k++
	}

	for p := 0; p < len(tmp); p++ {
		nums[left+p] = tmp[p]
	}

	return count
}

解法二：树状数组 + 离散化

核心思路：

将数组值离散化到 1..m 的索引区间。

从左到右扫描，对于当前值 x，查询已出现元素中大于 x 的数量。

用树状数组维护前缀计数即可。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于离散化与树状数组。

class Solution {
    public long minSwaps(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);

        Map<Integer, Integer> rank = new HashMap<>();
        int idx = 1;
        for (int num : sorted) {
            if (!rank.containsKey(num)) {
                rank.put(num, idx++);
            }
        }

        Fenwick tree = new Fenwick(rank.size());
        long ans = 0;

        for (int num : nums) {
            int pos = rank.get(num);
            long le = tree.query(pos);
            long seen = tree.query(rank.size());
            ans += seen - le;

            tree.add(pos, 1);
        }

        return ans;
    }

    static class Fenwick {
        private final long[] tree;

        Fenwick(int n) {
            tree = new long[n + 1];
        }

        void add(int idx, long delta) {
            for (int i = idx; i < tree.length; i += i & -i) {
                tree[i] += delta;
            }
        }

        long query(int idx) {
            long sum = 0;
            for (int i = idx; i > 0; i -= i & -i) {
                sum += tree[i];
            }
            return sum;
        }
    }
}

import "sort"

func minSwaps(nums []int) int64 {
	sorted := make([]int, len(nums))
	copy(sorted, nums)
	sort.Ints(sorted)

	rank := map[int]int{}
	idx := 1
	for _, num := range sorted {
		if _, ok := rank[num]; !ok {
			rank[num] = idx
			idx++
		}
	}

	bit := newFenwick(len(rank))
	ans := int64(0)

	for _, num := range nums {
		pos := rank[num]
		le := bit.query(pos)
		seen := bit.query(len(rank))
		ans += seen - le

		bit.add(pos, 1)
	}

	return ans
}

type fenwick struct {
	tree []int64
}

func newFenwick(n int) *fenwick {
	return &fenwick{tree: make([]int64, n+1)}
}

func (f *fenwick) add(idx int, delta int64) {
	for idx < len(f.tree) {
		f.tree[idx] += delta
		idx += idx & -idx
	}
}

func (f *fenwick) query(idx int) int64 {
	sum := int64(0)
	for idx > 0 {
		sum += f.tree[idx]
		idx -= idx & -idx
	}
	return sum
}

相似题目

题目	难度	考察点
493. 翻转对	困难	归并排序
315. 计算右侧小于当前元素的个数	困难	树状数组
327. 区间和的个数	困难	归并排序
775. 全局倒置与局部倒置	中等	逆序对
1649. 通过指令创建有序数组	困难	树状数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/42340608