Divisez les éléments d'un tableau trié en moins de groupes de sorte que la différence entre les éléments du nouveau tableau soit inférieure ou égale à 1

Parcourez le tableau. Chaque fois que la différence entre 2 éléments consécutifs est supérieure à 1, ajoutez 1 à votre variable de réponse.

`

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;
}

`

Comment dites-vous que votre approche n'est pas optimisée? Si votre est correct, alors selon votre approche, cela prend O (n) complexité de temps.

Mais vous pouvez utiliser la recherche binaire ici qui peut optimiser dans le cas moyen. Mais dans le pire des cas, cette recherche binaire peut prendre plus de O (n) complexité de temps.

Voici quelques conseils, Au fur et à mesure que le tableau est trié, vous choisirez une telle position dont la différence est au plus 1

La recherche binaire peut le faire de manière simple.

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;

Inspiré de la réponse de Faruk, si les valeurs sont contraintes d'être des entiers distincts, il existe une méthode éventuellement sous-linéaire.

En effet, si la différence entre deux valeurs est égale à la différence entre leurs index, ils sont garantis d'appartenir au même groupe et il n'est pas nécessaire de regarder les valeurs intermédiaires.

Vous devez organiser un parcours récursif du tableau, en pré-ordre. Avant de subdiviser un sous-tableau, vous comparez la différence d'index du premier et du dernier élément à la différence des valeurs, et ne subdivisez qu'en cas de non-concordance. Au fur et à mesure que vous travaillez en précommande, cela vous permettra d'émettre des morceaux des groupes dans un ordre consécutif, ainsi que de détecter les lacunes. Il faut prendre soin de fusionner les éléments des groupes.

Le pire des cas restera linéaire, car le parcours récursif peut dégénérer en un parcours linéaire (mais pas pire que cela). Le meilleur cas peut être meilleur. En particulier, si le tableau contient un seul groupe, il se trouvera au temps O (1). Si j'ai raison, pour chaque groupe de longueur entre 2 ^ n et 2 ^ (n + 1), vous épargnerez au moins 2 ^ (n-1) tests. (En fait, il devrait être possible d'estimer une complexité sensible à la sortie, égale à la longueur du tableau moins une fraction des longueurs de tous les groupes, ou similaire.)

Alternativement, vous pouvez travailler de manière non récursive, au moyen d'une recherche exponentielle: dès le début d'un groupe, vous commencez par un pas unitaire et doublez le pas à chaque fois, jusqu'à détecter un écart (différence de valeurs trop grande); puis vous redémarrez avec un pas unitaire. Là encore, pour les grands groupes, vous sauterez un nombre important d'éléments. Quoi qu'il en soit, le meilleur cas ne peut être que O (Log (N)).

Je suggérerais d'encoder des sous-ensembles dans un tableau de décalage défini comme suit:

• Les éléments de l'ensemble #i sont définis pour les indices j tels que offset [i]
• Le nombre de sous-ensembles est offset.size () - 1

Cela ne nécessite qu'une seule allocation de mémoire.

Voici une implémentation complète:

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

qui imprime:

XXX

Et comme il est toujours agréable de voir plus d'idées et de sélectionner celle qui vous convient le mieux, voici la solution simple en 6 lignes. Oui, c'est aussi O (n). Mais je ne suis pas sûr, si la surcharge des autres méthodes rend les choses plus rapides.

Veuillez voir:

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

Cela pourrait peut-être être une solution. . .