将大小为 n 的数组分成 k 个相同大小的组
array size n into k same size groups
我有一个大小为 n 的 unsorted 数组，我需要找到 k-1 除数，因此每个子集的大小都相同（就像数组排序后一样）。
我在 k-1=3 看到了这个问题。我想我需要中位数的中位数，这需要 o(n)。但我认为我们应该这样做 k 次所以 o(nk).
我想了解为什么需要 o(n logk).
例如：我有一个未排序的整数数组，我想找到第 k 个除数，它是将数组拆分为 k 个（相同大小的）的 k-1 个整数) 子数组根据它们的值。
如果我有 [1, 13, 6, 7, 81, 9, 10, 11]，则 3=k 分隔符是 [7 ,11] 拆分为 [1 6, 9 10 13 81]，其中每个子集都大到 2 且相等。
您可以使用分而治之的方法。首先，使用中位数算法找到第 (k-1)/2 个除法器。接下来，使用所选元素将列表划分为两个子列表。在每个子列表上重复该算法以找到剩余的分隔符。
最大递归深度为O(log k)，每个级别的所有子列表的总成本为O(n)，因此这是一个O(n log k)算法。
我有一个大小为 n 的 unsorted 数组，我需要找到 k-1 除数，因此每个子集的大小都相同（就像数组排序后一样）。
我在 k-1=3 看到了这个问题。我想我需要中位数的中位数，这需要 o(n)。但我认为我们应该这样做 k 次所以 o(nk).
我想了解为什么需要 o(n logk).
例如：我有一个未排序的整数数组，我想找到第 k 个除数，它是将数组拆分为 k 个（相同大小的）的 k-1 个整数) 子数组根据它们的值。
如果我有 [1, 13, 6, 7, 81, 9, 10, 11]，则 3=k 分隔符是 [7 ,11] 拆分为 [1 6, 9 10 13 81]，其中每个子集都大到 2 且相等。
您可以使用分而治之的方法。首先，使用中位数算法找到第 (k-1)/2 个除法器。接下来，使用所选元素将列表划分为两个子列表。在每个子列表上重复该算法以找到剩余的分隔符。
最大递归深度为O(log k)，每个级别的所有子列表的总成本为O(n)，因此这是一个O(n log k)算法。