Алгоритмы: распределять элементы далеко друг от друга

Question

У меня есть массив отсортированных целых чисел.Учитывая целое число N, мне нужно разместить N самых больших элементов дальше друг от друга, чтобы они имели максимальное расстояние между собой.Остальные элементы должны быть размещены между этими большими предметами.Например, массив из 10 с N = 3 приведет к [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,