0

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

Помогите модифицировать код.

Как я понимаю, нужно в основной код код вставить, что-то вроде этого.

 if (K == length_subset)

    {
        //Записать значения элементов в результирующий массив

        for (start_subset; start_subset < end_subset; start_subset++)
        {
            result_subset[k_j] = original_subset[start_subset];
            k_j++; //k здесь не меняется изначально, записывать начнет с того места, где было записано последнее
        }
        quantity_elements += length_subset; //увеличить количество элементов, т.к. добавлено множество
    }
}
2
  • вы лучше пример приведите то сделать надо. Пока не понятно почему нельзя взять любые K подряд элементов
    – pavel
    14 апр 2017 в 14:43
  • Например, массив длиной 5 и состоит из элементов 1,2,5,6,7. Если мы вводим K = 2, то он должен вывести 1,2 / 5,6 / 6,7. Если K = 3, то 5,6,7.
    – user241815
    14 апр 2017 в 14:47

1 ответ 1

1

Для решения данной задачи хорошо подходит принцип скользящего окна.

Для примера будем искать строго возрастающие последовательности длины 1 < K < N.

Если у нас есть упорядоченные K элементов, то убрав 1 сзади и добавив 1 спереди, достаточно сделать 1 сравнение для проверки что тут K подряд чисел.

Выводить буду только окончания данных отрезков.

int count = 1;
int prev = A[0]; 

for (int i=1; i < N; i++){
   if (A[i] = prev + 1)
      count ++;
   else
       count = 1;
   prev = A[i];
   if (count == K){
      count--;
      // i - ответ, делайте что надо.
   } 
}

Сложность алгоритма O(N).

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.