如何高效查找指定范围内的最小负载服务器索引

问题描述 #

实现一个函数，接收参数n（服务器数量）和requests（请求列表）：

• 初始时，长度为n的服务器数组所有元素均为0。
• 对于每个请求requests[i]，在范围[0, requests[i]]内找到值最小的服务器索引；若存在多个值相同的最小服务器，选择索引最小的那个。
• 将选中的索引存入结果列表，同时将对应服务器的值加1。

示例 #

n = 5 且 requests = [3, 2, 3, 2, 4]

结果：

[0,1,2,0,3]

示例解释 #

a) requests[0] = 3
初始服务器数组为 [0,0,0,0,0]，在范围[0,3]内选中索引0，结果列表变为[0]，服务器数组更新为[1,0,0,0,0]

b) requests[1] = 2
服务器数组为[1,0,0,0,0]，范围[0,2]内选中索引1，结果列表变为[0,1]，服务器数组更新为[1,1,0,0,0]

c) requests[2] = 3
服务器数组为[1,1,0,0,0]，范围[0,3]内选中索引2，结果列表变为[0,1,2]，服务器数组更新为[1,1,1,0,0]

d) requests[3] = 2
服务器数组为[1,1,1,0,0]，范围[0,2]内所有值相同，选索引最小的0，结果列表变为[0,1,2,0]，服务器数组更新为[2,1,1,0,0]

e) requests[4] = 4
服务器数组为[2,1,1,0,0]，范围[0,4]内选中索引3，结果列表变为[0,1,2,0,3]，服务器数组更新为[2,1,1,1,0]

约束条件 #

1 <= n <= 10^5
0 <= requests[i] < n

原始O(n²)实现（Java） #

import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println(solve(5, Arrays.asList(3,2,3,2, 4))); // 输出[0,1,2,0,3]
    }
     public static List<Integer> solve(int n, List<Integer> requests) {
        int[] servers = new int[n];
        List<Integer> result = new ArrayList<>();
        for (int e : requests) {
            int min = Integer.MAX_VALUE;
            int idx = -1;
            for (int i = 0; i <= e; i++) {
                if (servers[i] < min) {
                    min = servers[i];
                    idx = i;
                }
            }
            result.add(idx);
            servers[idx]++;
        }
        return result;
    }
}

优化方案：并查集实现O(m α(n))时间复杂度 #

核心思路 #

利用并查集记录每个服务器的「下一个可用候选」，避免每次遍历整个范围：

• 初始时，每个服务器的父节点是自身，代表它是当前可用的候选。
• 当服务器i被选中后，将它的父节点更新为i+1的根节点，下次查找时直接跳过该服务器，指向后续的候选。
• 对每个请求e，通过并查集快速找到[0,e]范围内符合要求的最小索引服务器，选中后更新并查集和服务器计数。

Java实现代码 #

import java.util.*;

public class OptimizedServerScheduler {
    private int[] parent;
    private int[] count;

    public List<Integer> solve(int n, List<Integer> requests) {
        parent = new int[n + 1]; // 多开一位处理边界情况
        count = new int[n];
        List<Integer> result = new ArrayList<>(requests.size());

        // 初始化并查集
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }

        for (int e : requests) {
            int root = find(e);
            result.add(root);
            count[root]++;
            // 将当前节点的父节点指向后续节点的根，实现"跳过已选节点"
            parent[root] = find(root + 1);
        }

        return result;
    }

    // 带路径压缩的查找，加速后续查询
    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

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

复杂度分析 #

• 时间复杂度：每个请求的查找操作是近似常数时间（路径压缩后的并查集操作时间复杂度为α(n)，α是阿克曼函数的反函数，增长极慢，可视为常数），总时间复杂度为O(m α(n))，完全适配n和m达1e5的规模。
• 空间复杂度：O(n)，用于存储并查集父节点数组和服务器计数数组。

内容的提问来源于stack exchange，提问作者Sid