算法问题：将数组中指定数量的最大元素尽可能分散放置

问题说明 #

给定一个已经排好序的整数数组，指定一个整数N，我们需要把数组里N个最大的元素尽可能分散开，让它们之间的间距最大，剩下的元素再填充到这些大元素的空隙里。举个例子，长度为10的数组，当N=3时，最终结果可以是[0, 5, 8, 2, 6, 9, 3, 7, 10, 4]（这里的输入数组是降序的{10,9,8,7,6,5,4,3,2,1}，最大的3个元素就是10、9、8）。

Java实现代码 #

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] start = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        int[] end = new int[10];
        int N = 4;
        int step = Math.round(start.length / N);
        int count = 0;
        
        for (int i = 0; i < step; i++) {
            for (int j = i; j < start.length; j = j + step) {
                if (count < start.length) {
                    end[j] = start[count];
                    count++;
                }
            }
        }
        // 修正原代码的输出问题，用Arrays.toString才能打印数组内容
        System.out.println(Arrays.toString(end));
    }
}

代码思路拆解 #

我给你捋捋这段代码的逻辑：

• 输入的start数组是降序排列的，所以从前往后取的元素就是从大到小的，前N个自然是最大的N个元素
• 计算步长step：用数组长度除以N再取整，这个步长就是我们放置元素的间隔，能保证最大的元素被均匀分散到数组里
• 双层循环的作用：外层循环控制起始的偏移位置，内层循环按步长跳着填充元素。这样一来，最大的元素会先被放到间隔开的位置上，剩下的元素再依次填充到空隙里，刚好满足"最大元素间距最大"的要求

小提示：原代码里的start[count] != 0判断其实没必要，因为输入数组里没有0元素，而且count是严格小于数组长度的，所以可以去掉这个条件；另外原代码用end.toString()只会打印数组的对象地址，换成Arrays.toString(end)才能输出数组的实际内容哦。

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