Задача: Учитывая массив целых чисел и число k, где 1 <= k <= длина массива, вычислить максимальные значения каждого подмассива длины k.</p>
Сделайте это за время O (n) и пространство O (k).Вы можете изменить входной массив на месте, и вам не нужно сохранять результаты.Вы можете просто распечатать их по мере их вычисления.
Пример: Данный массив = [10, 5, 2, 7, 8, 7] и k = 3, мыдолжно получить: [10, 7, 8, 8], так как:
10 = максимум (10, 5, 2)
7 = максимум (5, 2, 7)
8 = максимум (2, 7, 8)
8 = максимум (7, 8, 7)
Идея:
Iподумал об использовании функции std :: max_element () для решения этой проблемы, в которой я заметил шаблон.Используя приведенный выше пример
std :: max_element (0, 2) = 10, когда 0 - начальная позиция, а 2 - конечная позиция итератора.
std :: max_element (1,3) = 7
std :: max_element (2, 4) = 8
std :: max_element (3,5) = 8
Таким образом, для любого k первыйИтератор всегда будет от 0 до n-2, где n - размер вектора или массива, а правильный итератор max_element всегда будет от k-1 до n-1.
Хотя он не слишком прямойвперед, указав правильный итератор для различных значений k.Как вы можете видеть из моего кода, я придерживался этой части, но я считаю, что моя идея обоснована.Я надеюсь, что проиллюстрировал эту идею, чтобы другие ее поняли.
Код:
#include <iostream>
#include <vector>
#include <random>
#include <ctime>
// Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values
// of each subarray of length k.
// For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get : [10, 7, 8, 8], since :
// 10 = max(10, 5, 2)
// 7 = max(5, 2, 7)
// 8 = max(2, 7, 8)
// 8 = max(7, 8, 7)
// Do this in O(n) time and O(k) space. You can modify the input array in-place and you do not need to
// store the results. You can simply print them out as you compute them.
void printKMax(std::vector<int>& nums, int k)
{
int n = nums.size();
int i = 0;
int j = k - 1;
std::vector<int>::iterator it;
while (j <= n - 1)
{
it = std::max_element(nums.begin() + i, );
i++;
j++;
std::cout << *it << " ";
}
}
int main()
{
std::vector<int> nums = { 10, 5, 2, 7, 8, 7};
int k = 3;
printKMax(nums, k);
std::cin.get();
}
Вопрос: У меня проблемы с поиском формулы дляправая часть std :: max_element для работы при различных значениях k.Любая помощь будет принята с благодарностью.