c++ - 将排序数组的元素分成最少数量的组，使得新数组的元素之间的差异小于或等于 1

Question

如何将数组中的元素分成最少数量的数组，使得每个组成的数组的元素值相差不超过1？

假设我们有一个数组:[4, 6, 8, 9, 10, 11, 14, 16, 17]。数组元素已排序。

我想将数组的元素分成最少数量的数组，使得结果数组中的每个元素相差不超过 1。

在这种情况下，分组将是:[4]、[6]、[8、9、10、11]、[14]、[16、17]。所以总共会有 5 个组。

我怎样才能写一个程序呢？或者您也可以建议算法。

我尝试了天真的方法:获取数组的连续元素之间的差异，如果差异小于(或等于)1，我将这些元素添加到新 vector 中。然而，这种方法非常未优化，并且直接无法显示大量输入的任何结果。

实际代码实现:

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;

int main() {

    int num = 0, buff = 0, min_groups = 1;    // min_groups should start from 1 to take into account the grouping of the starting array element(s)
    cout << "Enter the number of elements in the array: " << endl;
    cin >> num;

    vector<int> ungrouped;
    cout << "Please enter the elements of the array: " << endl;
    for (int i = 0; i < num; i++)
    {
        cin >> buff;
        ungrouped.push_back(buff);
    }

    for (int i = 1; i < ungrouped.size(); i++)
    {
        if ((ungrouped[i] - ungrouped[i - 1]) > 1)
        {
            min_groups++;
        }
    }

    cout << "The elements of entered vector can be split into " << min_groups << " groups." << endl;

    return 0;
}

Answer 1

受法鲁克回答的启发，如果值被限制为不同的整数，则可能存在次线性方法。

确实，如果两个值之间的差值等于它们索引之间的差值，则可以保证它们属于同一组，并且无需查看中间值。

您必须按预定顺序组织数组的递归遍历。在 segmentation 子数组之前，您将第一个和最后一个元素的索引差异与值的差异进行比较，只有在不匹配的情况下才 segmentation 。当您按预定顺序工作时，这将允许您按连续顺序发射组的各个部分，并检测间隙。必须小心合并各个组的各个部分。

最坏的情况将保持线性，因为递归遍历可以退化为线性遍历(但不会比这更糟)。最好的情况可以更好。特别是，如果数组包含单个组，则将在 O(1) 的时间内找到它。如果我是对的，对于 2^n 和 2^(n+1) 之间的每一组长度，您将至少进行 2^(n-1) 次测试。 (事实上​​ ，应该可以估计一个输出敏感的复杂度，等于数组长度减去所有组长度的分数，或类似的。)

---

或者，您可以通过指数搜索以非递归方式工作:从一组的开始，您从一个单位步长开始，每次加倍步长，直到您检测到间隙(值的差异太大了);然后你重新开始一个单位步骤。同样，对于大型组，您将跳过大量元素。反正最好的情况只能是O(Log(N))。