如何优化寻找排序顺序最小操作数的算法至低于O(n²)时间复杂度？

AI 小北

2026-6-14

算法优化方案：将O(n²)复杂度降至O(n)

问题回顾

给定包含1到n不同数字的数组，按规则统计操作数：每次从左到右遍历数组，找到当前order值则递增order，遍历结束算一次操作；重复直到order达到n，操作次数即为结果。原Java实现采用多次全数组遍历，时间复杂度O(n²)，现优化为O(n)复杂度。

核心思路

操作数的本质可转化为统计连续递增数对(k, k+1)中，k的位置大于k+1位置的次数，最终操作数等于该次数+1。原因是：

若k在k+1的右侧，当我们在某次操作中找到k时，已经遍历过k+1所在的左侧区域，无法在同一次操作中找到k+1，必须开启新操作。
初始操作数为1（至少需要一次遍历），每出现一次上述情况，操作数加1。

优化后的Java实现

import java.util.*;

class Main {
    public static int solve(List<Integer> arr) {
        int n = arr.size();
        // 记录每个数字的索引位置，数字范围1~n，数组下标对应数字值
        int[] pos = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pos[arr.get(i)] = i;
        }
        
        int operations = 1;
        // 遍历连续数对(k, k+1)
        for (int k = 1; k < n; k++) {
            // 如果k的位置在k+1右侧，需要新增操作
            if (pos[k] > pos[k + 1]) {
                operations++;
            }
        }
        return operations;
    }

    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(5, 3, 4, 1, 2))); // 输出: 3
        System.out.println(solve(Arrays.asList(3,1,4,2,5))); // 输出: 2
        System.out.println(solve(Arrays.asList(1,2,3,4))); // 输出: 1
        System.out.println(solve(Arrays.asList(2,1))); // 输出: 2
    }
}