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).

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.