如何将一个长度为 n 的数组分成 k 个大小大致相等的子数组（在 C 中）？

Question

我有一个大小为n的数组，想分成k个子数组，每个数组的大小必须大致相同。我想了一会儿，知道你必须使用两个 for 循环，但我很难实现这些 for 循环。

我尝试过的：

//Lets call the original integer array with size n: arr
// n is the size of arr
// k is the number of subarrays wanted

int size_of_subArray = n/k;
int left_over = n%k; // When n is not divisible by k
int list_of_subArrays[k][size_of_subArray + 1];

//Lets call the original integer array with size n: arr

for(int i = 0; i < k; i++){
   for(int j = 0; j < size_of_subArray; j++){
       list_of_subArrays[i][j] = arr[j];
   }
}

我正在努力在 forloop 中获取正确的索引。

有什么想法吗？

Answer 1

我已经重构了你的代码并对其进行了注释。

要点是：

计算子数组大小时，必须向上取整
arr的索引需要从0继续递增（即不是重置为0）

以下应该有效，但我没有测试它[请原谅无偿样式清理]：

// Lets call the original integer array with size n: arr
//  n is the size of arr
//  k is the number of subarrays wanted

// round up the size of the subarray
int subsize = (n + (k - 1)) / k;

int list_of_subArrays[k][subsize];

int arridx = 0;
int subno = 0;

// process all elements in original array
while (1) {
    // get number of remaining elements to process in arr
    int remain = n - arridx;

    // stop when done
    if (remain <= 0)
        break;

    // clip remaining count to amount per sub-array
    if (remain > subsize)
        remain = subsize;

    // fill next sub-array
    for (int subidx = 0; subidx < remain; ++subidx, ++arridx)
        list_of_subArrays[subno][subidx] = arr[arridx];

    // advance to next sub-array
    ++subno;
}

更新：

Yes this divides the arrays into n subarrays, but it doesn't divide it evenly. Say there was an array of size 10, and wanted to divide it into 9 subarrays. Then 8 subarrays will have 1 of original array's element, but one subarray will need to have 2 elements.

您的原始代码有一些错误[已在上面的示例中修复]。即使我是为自己做这件事，上面的内容也是开始工作的第一步。

在你原来的问题中，你确实说："and each array must have approximately the same size"。但是，这里有列表子数组的物理大小[仍然是向上舍入的值]。

但是，我可能会说 "evenly distributed" 之类的话来进一步阐明您的意图。也就是说，您希望最后一个 sub-array/bucket 到 而不是 是 "short" [大幅度]。

鉴于此，代码开始时有些相同，但需要更复杂一些。这仍然有点粗糙，可能会进一步优化：

#include <stdio.h>

#ifdef DEBUG
#define dbgprt(_fmt...)     printf(_fmt)
#else
#define dbgprt(_fmt...)     /**/
#endif

int arr[5000];

// Lets call the original integer array with size n: arr
//  n is the size of arr
//  k is the number of subarrays wanted

void
fnc2(int n,int k)
{
    // round up the size of the subarray
    int subsize = (n + (k - 1)) / k;

    int list_of_subArrays[k][subsize];

    dbgprt("n=%d k=%d subsize=%d\n",n,k,subsize);

    int arridx = 0;

    for (int subno = 0;  subno < k;  ++subno) {
        // get remaining number of sub-arrays
        int remsub = k - subno;

        // get remaining number of elements
        int remain = n - arridx;

        // get maximum bucket size
        int curcnt = subsize;

        // get projected remaining size for using this bucket size
        int curtot = remsub * curcnt;

        // if we're too low, up it
        if (curtot < remain)
            ++curcnt;

        // if we're too high, lower it
        if (curtot > remain)
            --curcnt;

        // each bucket must have at least one
        if (curcnt < 1)
            curcnt = 1;

        // each bucket can have no more than the maximum
        if (curcnt > subsize)
            curcnt = subsize;

        // last bucket is the remainder
        if (curcnt > remain)
            curcnt = remain;

        dbgprt("  list[%d][%d] --> arr[%d] remain=%d\n",
            subno,curcnt,arridx,remain);

        // fill next sub-array
        for (int subidx = 0; subidx < curcnt; ++subidx, ++arridx)
            list_of_subArrays[subno][subidx] = arr[arridx];
    }

    dbgprt("\n");
}

如何将一个长度为 n 的数组分成 k 个大小大致相等的子数组（在 C 中）？

How to divide an array of n length into k sub arrays that have approximately equal sizes (in C)?

c

arrays

sub-array