好朋友的笔试题——1000个1-100随机数尽可能均匀分配区间的问题

RenShiWei 2021/11/4 算法

作者：duktig

博客：https://duktig.cn (opens new window) （文章首发）

优秀还努力。愿你付出甘之如饴，所得归于欢喜。

本篇文章算法题源码参看：https://github.com/duktig666/algorithm/blob/0822384cdddb52058a9d2f989842689e2f4653d2/src/interview/IntervalQuestion20211104.java (opens new window)

好朋友笔试的一道算法题，感觉很有意思，特此写一下如何实现？

# 题目

区间分配算法题

区间分配问题

给定一个List<Integer> numList, 他的 size为1000，每一个numList的元素随机从1-100取值(取值内容为整数)，然后将numList中的元素从小到大排序，排除掉最大的10%的元素后;在numList剩下的90%的元素中,取最大值maxValue和最小值 minValue，将区间[minValue, maxValue]分成9个区间（尽量保证每个区间的宽度相等或接近);在这9个区间中，统计numList中的元素分别落在每个区间中的个数。

# 思路

# 第一步：初始化一个1000个1-100随机数的集合

/**
 * 初始化1000个元素的几个，每个元素是1-100的随机数
 *
 * @return 1000个随机数的集合
 */
private List<Integer> init() {
    List<Integer> list = new ArrayList<>(1000);
    for (int i = 0; i < 1000; i++) {
        list.add((int) (Math.random() * 100 + 1));
    }
    return list;
}

1
2
3
4
5
6
7
8
9
10
11
12

# 第二步：对集合进行排序，并提出最大的10%的元素

/**
 * 排序并且剔除集合中最大的10%的元素
 */
private List<Integer> prepare() {
    // 初始化1000个随机数集合
    List<Integer> randomList = this.init();
    // 排序
    Collections.sort(randomList);
    // 剔除集合中最大的10%的元素
    return randomList.subList(0, 900);
}

1
2
3
4
5
6
7
8
9
10
11

现在准备工作已经准备好，下面就是重点了——如何进行分区？

# 第三步：分区算法的实现

理想分区方法：总共900个元素，分9个区，每个分区100个元素。
所以，按照理想的分享，每次尝试取100个元素（临界下标criticalIndex）
遇到直观的问题就是，在第100个元素可能与左侧或者右侧元素相等，那么必然面临将这个临界值分配给左分区还是给右分区的问题。
1. 统计这个临界值在左区间和右区间出现的次数
2. 左区间出现多，分配在左区间。右区间出现多，这个值分配在右区间
每次分配过后，需要对数据进行从新计算
1. 记录上一次区间的临界值，方便计算数量
2. 计算下一个区间的临界值（默认+100）
处理整个计算的临界值情况

具体实现参看如下代码：

public void distributeInterval() {
    // 取出90%最大元素的集合
    List<Integer> randomList = this.prepare();
    // 每次分区的临界值
    int criticalValue;
    // 每次分区的临界索引（第100个元素）
    int criticalIndex = 99;
    int nextInterval = 0;
    // 分配9个区间
    for (int i = 1; i < 10; i++) {
        criticalValue = randomList.get(criticalIndex);
        // 计算临界值应该放在左区间还是右区间
        int leftCount = 0, rightCount = 0;
        int leftIndex = criticalIndex, rightIndex = criticalIndex;
        // 左区间统计
        while (leftIndex > 0 && criticalValue == randomList.get(leftIndex)) {
            leftIndex--;
            leftCount++;
        }
        // 右区间统计
        while (rightIndex < 900 && criticalValue == randomList.get(rightIndex)) {
            rightIndex++;
            rightCount++;
        }
        // 临界值左边数量多，放左边；反之亦然 criticalIndex = rightIndex(大的索引，即放左边的意思)
        criticalIndex = leftCount >= rightCount ? rightIndex : leftIndex;
        //当前区间元素数量
        int countInterval = criticalIndex - nextInterval;
        System.out.println(countInterval);
        // 分区计算完后，重置下一次计算的数据
        nextInterval = criticalIndex;
        criticalIndex = criticalIndex + 100 < 900 ? criticalIndex + 100 : 899;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 完整代码

public class IntervalQuestion20211104 {

    /**
     * 初始化1000个元素的几个，每个元素是1-100的随机数
     *
     * @return 1000个随机数的集合
     */
    private List<Integer> init() {
        List<Integer> list = new ArrayList<>(1000);
        for (int i = 0; i < 1000; i++) {
            list.add((int) (Math.random() * 100 + 1));
        }
        return list;
    }

    /**
     * 排序并且剔除集合中最大的10%的元素
     */
    private List<Integer> prepare() {
        // 初始化1000个随机数集合
        List<Integer> randomList = this.init();
        // 排序
        Collections.sort(randomList);
        // 剔除集合中最大的10%的元素
        return randomList.subList(0, 900);
    }

    /**
     * 分区算法：
     * 1. 理想分区，每个分区100个元素，每次尝试取100个元素（临界下标criticalIndex）
     * 2. 相邻区间，临界值的分配问题
     * ① 同一个数既在左区间，又在右区间怎么分配？
     * ② 统计这个临界值在左区间和右区间出现的次数
     * ③ 左区间出现多，分配在左区间。右区间出现多，这个值分配在右区间
     * 3. 每次分配完成后，计算重要数据如下：
     * ① 记录上一次区间的临界值，方便计算数量
     * ② 计算下一个区间的临界值（默认+100）
     * 4. 处理整个计算的临界值情况
     */
    public void distributeInterval() {
        // 取出90%最大元素的集合
        List<Integer> randomList = this.prepare();
        // 每次分区的临界值
        int criticalValue;
        // 每次分区的临界索引（第100个元素）
        int criticalIndex = 99;
        int nextInterval = 0;
        // 分配9个区间
        for (int i = 1; i < 10; i++) {
            criticalValue = randomList.get(criticalIndex);
            // 计算临界值应该放在左区间还是右区间
            int leftCount = 0, rightCount = 0;
            int leftIndex = criticalIndex, rightIndex = criticalIndex;
            // 左区间统计
            while (leftIndex > 0 && criticalValue == randomList.get(leftIndex)) {
                leftIndex--;
                leftCount++;
            }
            // 右区间统计
            while (rightIndex < 900 && criticalValue == randomList.get(rightIndex)) {
                rightIndex++;
                rightCount++;
            }
            // 临界值左边数量多，放左边；反之亦然 criticalIndex = rightIndex(大的索引，即放左边的意思)
            criticalIndex = leftCount >= rightCount ? rightIndex : leftIndex;
            //当前区间元素数量
            int countInterval = criticalIndex - nextInterval;
            System.out.println(countInterval);
            // 分区计算完后，重置下一次计算的数据
            nextInterval = criticalIndex;
            criticalIndex = criticalIndex + 100 < 900 ? criticalIndex + 100 : 899;
        }
    }

    /**
     * 测试
     */
    public static void main(String[] args) {
        IntervalQuestion20211104 test = new IntervalQuestion20211104();
        test.distributeInterval();
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

结果：

1
2
3
4
5
6
7
8
9

# 总结

这道算法题算是比较考验思路和细节的（临界值问题），如何将这900个1-100的随机数尽可能均分配到9个区间当中，每个人可能有不同的思路。

上边的实现方法，应该是在有限的时间里思考，优化一定的时空复杂度，并且经过测试还算浮动不大的一种实现。

但是这道题很考验细节和临界值问题，以上实现还有很多问题，还可以进一步地进行优化，例如：

极端情况下，如果出现900个一样的数字怎么办？
如果一个数字频繁出现怎么办？比如出现了500次
如果上述算法的临界值，在第一次分配区间时在第50号元素假设8出现了100次怎么办？如果分配给左边，那么左边就是150个元素；如果分配给右边，那么左边就是50个元素，很有可能造成倾斜。

虽然以上列举的例子在数据量是900的情况下，出现的概率极低，但并不是代表不可能出现。所以这道题要想考虑全面是比较难的，重点的就是，在有限的时间尽可能保证可靠性。

Duktig

Choose mode