Разделите элементы отсортированного массива на наименьшее количество групп так, чтобы разница между элементами нового массива была меньше или равна 1

Question

Как разделить элементы в массиве на минимальное количество массивов, чтобы разница между значениями элементов каждого из сформированных массивов не отличалась более чем на 1?

* 1004Допустим, у нас есть массив: [4, 6, 8, 9, 10, 11, 14, 16, 17].Элементы массива отсортированы.

Я хочу разделить элементы массива на минимальное количество массивов, чтобы каждый из элементов в результирующих массивах не отличался более чем на 1.

В этом случае группировки будут: [4], [6], [8, 9, 10, 11], [14], [16, 17].Таким образом, было бы всего 5 групп.

Как я могу написать программу для того же самого?Или вы можете также предложить алгоритмы.

Я попробовал наивный подход: получить разницу между последовательными элементами массива и, если разница меньше (или равна) 1, я добавляю эти элементы в новыйвектор.Однако этот метод очень неоптимизирован , и при прямом наборе не отображаются результаты для большого количества входов.

Реальная реализация кода:

#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

Вдохновленный ответом Фарука, если значения ограничены различными целыми числами, возможно, существует сублинейный метод.

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

Вы должны организовать рекурсивный обход массива в предзаказе.Прежде чем подразделить подрешетку, вы сравниваете разность индексов первого и последнего элемента с разностью значений и делите ее только в случае несоответствия.Поскольку вы работаете в предзаказе, это позволит вам генерировать фрагменты групп в последовательном порядке, а также обнаруживать пробелы.Нужно быть осторожным, чтобы объединить части групп.

Наихудший случай останется линейным, потому что рекурсивный обход может выродиться в линейный обход (но не хуже этого).В лучшем случае может быть лучше.В частности, если массив содержит одну группу, он будет найден за время O (1).Если я прав, для каждой группы длины от 2 ^ n до 2 ^ (n + 1) вы сэкономите не менее 2 ^ (n-1) тестов.(На самом деле, должна быть возможность оценить чувствительность к выходу, равную длине массива за вычетом доли длин всех групп или аналогичной.)

---

В качестве альтернативы, вы можете работать внерекурсивный способ с помощью экспоненциального поиска: с начала группы вы начинаете с единичного шага и удваиваете шаг каждый раз, пока не обнаружите разрыв (слишком большая разница в значениях);затем вы перезапустите с шагом в единицу.Здесь снова, для больших групп вы пропустите значительное количество элементов.В любом случае, лучшим вариантом может быть только O (Log (N)).

Answer 2

Я бы предложил кодировать подмножества в массив смещений, определенный следующим образом:

• Элементы для набора #i определены для индексов j, таких, что смещение [i] <= j <смещение [i + 1] </li>
• Число подмножеств является offset.size () - 1

Это требует только одного выделения памяти.

Вот полная реализация:

#include <cassert>
#include <iostream>
#include <vector>

std::vector<std::size_t> split(const std::vector<int>& to_split, const int max_dist = 1)
{
  const std::size_t to_split_size = to_split.size();
  std::vector<std::size_t> offset(to_split_size + 1);
  offset[0] = 0;
  size_t offset_idx = 1;
  for (std::size_t i = 1; i < to_split_size; i++)
  {
    const int dist = to_split[i] - to_split[i - 1];
    assert(dist >= 0);  // we assumed sorted input
    if (dist > max_dist)
    {
      offset[offset_idx] = i;
      ++offset_idx;
    }
  }
  offset[offset_idx] = to_split_size;
  offset.resize(offset_idx + 1);
  return offset;
}

void print_partition(const std::vector<int>& to_split, const std::vector<std::size_t>& offset)
{
  const std::size_t offset_size = offset.size();
  std::cout << "\nwe found " << offset_size-1 << " sets";
  for (std::size_t i = 0; i + 1 < offset_size; i++)
  {
    std::cout << "\n";
    for (std::size_t j = offset[i]; j < offset[i + 1]; j++)
    {
      std::cout << to_split[j] << " ";
    }
  }
}

int main()
{
  std::vector<int> to_split{4, 6, 8, 9, 10, 11, 14, 16, 17};
  std::vector<std::size_t> offset = split(to_split);
  print_partition(to_split, offset);
}

который печатает:

we found 5 sets
4 
6 
8 9 10 11 
14 
16 17 

Answer 3

И так как всегда приятно видеть больше идей и выбирать ту, которая подходит вам лучше всего, вот прямое 6-строчное решение.Да, это также O (n).Но я не уверен, что из-за накладных расходов на другие методы это ускорится.

Пожалуйста, смотрите:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iterator>

using Data = std::vector<int>;
using Partition = std::vector<Data>;

Data testData{ 4, 6, 8, 9, 10, 11, 14, 16, 17 };

int main(void)
{
    // This is the resulting vector of vectors with the partitions
    std::vector<std::vector<int>> partition{};  
    // Iterating over source values
    for (Data::iterator i = testData.begin(); i != testData.end(); ++i) {
        // Check,if we need to add a new partition
        // Either, at the beginning or if diff > 1
        // No underflow, becuase of boolean shortcut evaluation
        if ((i == testData.begin()) || ((*i) - (*(i-1)) > 1)) {
            // Create a new partition
            partition.emplace_back(Data());
        }
        // And, store the value in the current partition
        partition.back().push_back(*i);
    }

    // Debug output:  Copy all data to std::cout
    std::for_each(partition.begin(), partition.end(), [](const Data& d) {std::copy(d.begin(), d.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; });

    return 0;
}

Возможно, это может быть решением.,.

Answer 4

Итерация по массиву.Если разница между двумя последовательными элементами больше 1, добавьте 1 к переменной ответа.

`

int getPartitionNumber(int arr[]) {
    //let n be the size of the array;
    int result = 1;
    for(int i=1; i<n; i++) {
        if(arr[i]-arr[i-1] > 1) result++;
    }
    return result;
}

`

Answer 5

Как вы говорите, ваш подход не оптимизирован?Если вы правы, то, согласно вашему подходу, это займет O(n) сложность времени.

Но вы можете использовать здесь бинарный поиск, который может оптимизировать в среднем случае.Но в худшем случае этот двоичный поиск может занять более чем O(n) сложность времени.

Вот подсказки. Поскольку массив отсортирован, вы выберете такую ​​позицию, разница которой составляет не более 1 .

Двоичный поиск может сделать это простым способом.

int arr[] = [4, 6, 8, 9, 10, 11, 14, 16, 17];

int st = 0, ed = n-1; // n = size of the array.
int partitions = 0;
while(st <= ed) {
    int low = st, high = n-1;
    int pos = low;
    while(low <= high) {
        int mid = (low + high)/2;
        if((arr[mid] - arr[st]) <= 1) {
            pos = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    partitions++;
    st = pos + 1;
}
cout<< partitions <<endl;

В среднем это лучше, чем O(n).Но в худшем случае (где ответ будет равен n ), потребуется O(nlog(n)) время.