c - 如何将 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

我重构了您的代码并对其进行了注释。

要点是:

1. 计算子数组大小时，必须向上取整
2. 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.

您的原始代码有一些错误[在上面的示例中已修复]。即使我是为自己做这件事，上述也是让事情发挥作用的第一步。

在您最初的问题中，您确实说:“每个数组的大小必须大约相同”。但是，这里有列表子数组的物理大小[仍然是向上舍入的值]。

但是，我可能会说“均匀分布”之类的话来进一步阐明您的意图。也就是说，您希望最后一个子数组/存储桶不“短”[大幅]。

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

#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");
}