算法 : distribute elements far away from each other

Question

我有一个排序整数数组。给定一个整数 N i 需要将 N 个最大的元素彼此远离放置，以便它们彼此之间具有最大的空间。其余元素应放在这些大项目之间。例如，N=3 的 10 数组将导致 [0, 5, 8, 2, 6, 9, 3, 7, 10, 4]。

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 y = 0;
    int count = 0;

    for (int i = 0; i < step; i++) {
        for (int j = i; j<start.length; j = j + step) {
            //System.out.println(j + " " + i);
            if (count < start.length && start[count] != 0) {
                end[j] = start[count];
                count++;
            }
        }

    }
    System.out.println(end.toString());

}

Answer 1

你有一个 K 元素的数组。您有 N 个需要分发的最大数量。然后:

1. Step := K/N(去除余数)
2. 从最大 N 中取出任意数并将其插入到 Step/2 位置。
3. 取其他最大数并将其插入到前一个插入的最大数之后 Step 距离处。

给出 [1,2,3,4,5,6,7,8,9,10]。所以 K = 10，N = 3。然后是Step = 3。所以第一个最大值放在3/2位置

[1,10,2,3,4,5,6,7,8,9]

然后其他 2 被放置在 3 距离:

[1,10,2,3,9,4,5,8,6,7]

代码:

std::vector<int> Distribute(std::vector<int> aSource, int aNumber)
{
    auto step = aSource.size() / aNumber; // Note integer dividing.
    for (int i = 0; i < aNumber; ++i)
    {
        auto place = aSource.end() - i * step - step / 2;
        aSource.insert(place, aSource.front());
        aSource.erase(aSource.begin());
    }
    return aSource;
}

int main()
{
    std::vector<int> vec{10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10};
    auto res = Distribute(vec, 4);
    for (auto e : res)
    {
        std::cout << e << ", ";
    }
    std::cout << std::endl;
}

输出:

6, 5, 4, 7, 3, 2, 1, 0, 8, -1, -2, -3, -4, 9, -5, -6, -7, -8, 10, -9, -10,