Разбить массив длинной N на k подмассивов, что бы длина самого короткого и длинного подмассива отличалась на 1

Question

Это тест от работодателя, нужно описать алгоритм решения задачи на языке с#. Можно на каком то другом, если будет понятно для шарписта или описаны функции.
Опишите алгоритм разбиения массива длины N на k подмассивов так, чтобы размер самого длинного и самого короткого подмассива отличалась не больше чем на 1.
Может ли k быть больше длины N?
Чему будут равны длины подмассивов?

Answer 1

Берете N и делите на k нацело.

int a = N / k;

получаете минимальную длину подмассива

а остаток от деления

int b = N % k;

распределяете по одному на каждый из массивов, на сколько хватит, то есть добавляете к b массивов единицу к длине.

Вот решение "в лоб", возможно можно как-то покрасивее сделать, но я решил больше 5 минут на написание кода не тратить.

static int[][] SplitArray(int[] array, int k)
{
    int index = 0;
    int N = array.Length;
    int a = N / k;
    int b = N % k;
    int[][] result = new int[k][];

    for (int i = 0; i < k; i++)
    {
        int length = a;
        if (b > 0)
        {
            length++;
            b--;
        }
        result[i] = new int[length];
        for (int j = 0; j < length; j++)
        {
            result[i][j] = array[index++];
        }
    }

    return result;
}

Пример

static void Main(string[] args)
{
    int[] array = new int[] { 1, 2, 3, 4, 5 };
    int[][] result = SplitArray(array, 3);

    for (int i = 0; i < result.Length; i++)
    {
        Console.WriteLine(string.Join(" ", result[i]));
    }
}

Вывод в консоль

1 2
3 4
5

Может ли k быть больше длины N?

Очевидно, нет.

Answer 2

Как альтернативный вариант.

Предположу, что не важно как именно распределятся данные, но важно их количество.

Тогда решение можно упростить, хотя идея та же самая

int[] split(int N, int k)
{
    int[] ret = new int[k];
    int distract = N / k;
    N = N % k;
    
    for (int i = 0; i < k; i++)
        ret[i] = distract;
    
    int index = 0;
    while (N > 0)
    {
        ret[index++] += 1;
        N--;
    }
    return ret;
}

Плюсы этого алгоритма:

не надо перебирать все данные в массиве, да и массива то нет, важно только количество элементов
по скорости будет пропорционально K (второй ответ тут пропорционален N)
по памяти также пророрционален K (второй ответ тут пропорционален N * k)

проверка

Console.WriteLine(string.Join(", ", split(6, 4)));
Console.WriteLine(string.Join(", ", split(10, 4)));
Console.WriteLine(string.Join(", ", split(10, 5)));

Результат

2, 2, 1, 1
3, 3, 2, 2
2, 2, 2, 2, 2

БЛОГ НА HUSL

Разбить массив длинной N на k подмассивов, что бы длина самого короткого и длинного подмассива отличалась на 1

Ответы (2 шт):