如何高效判断两个数组是否相似（最多允许交换1对元素）

云原生阿岚

2026-10-1

数组相似性判断代码优化方案

原代码性能瓶颈

现有代码的核心耗时来自两次Arrays.sort()排序操作，时间复杂度为O(n log n)，处理大长度数组时排序开销会急剧上升，是拖慢执行速度的主要原因。

优化思路

完全移除排序步骤，改为单次遍历完成判断，时间复杂度降到O(n)，逻辑如下：

前置判断：两个数组长度不一致直接返回false
遍历数组时统计不相等的元素个数，同时记录前两处不相等的索引位置
不相等个数为0：数组本身完全相同，返回true
不相等个数不等于2：单次交换最多只能修正2个位置的不匹配，直接返回false
不相等个数恰好为2：校验两个位置的元素是否交叉相等（即a的第一个不同元素等于b的第二个不同元素，a的第二个不同元素等于b的第一个不同元素），满足则返回true，否则返回false

优化后代码

boolean checkSimilarArray(int[] a, int[] b) {
    // 前置判断长度是否一致
    if (a.length != b.length) {
        return false;
    }
    int diffCount = 0;
    int firstDiffIdx = -1, secondDiffIdx = -1;
    for (int i = 0; i < a.length; i++) {
        if (a[i] != b[i]) {
            diffCount++;
            // 超过2个不同直接提前返回，无需继续遍历
            if (diffCount > 2) {
                return false;
            }
            if (diffCount == 1) {
                firstDiffIdx = i;
            } else {
                secondDiffIdx = i;
            }
        }
    }
    // 没有不同直接返回true
    if (diffCount == 0) {
        return true;
    }
    // 仅2个不同的场景校验交叉相等
    return a[firstDiffIdx] == b[secondDiffIdx] && a[secondDiffIdx] == b[firstDiffIdx];
}