Учитывая список и число k, инвертируйте первые k элементов и оставьте следующие k элементов. Повторите это во всем списке. Инвертируя, я имею в виду, меняя знак числа.
Это был вопрос интервью на Amazon, который я просматриваю на веб-сайте, и я пытался приблизиться к нему, просто подумав о том, как его решить, конечно, я также хотел бы узнать самый быстрый алгоритм для его решения и ваших идей.
Я думал о разделении массива на K-Steps, затем инвертировал, пропускал. Затем объедините массивы, как при сортировке слиянием.
for (int i=0;i<size;i+=k*2)
for (int j=0;j<k&&i+j<size;j++)
arr[i+j]=-arr[i+j];
если вы уверены, что размер массива кратен 2 * k или равен x * 2 * k - k, тогда:
for (int i=0;i<size;i+=k*2)
for (int j=0;j<k;j++)
arr[i+j]=-arr[i+j];
Сложность решения хэсана:
Поскольку вы сказали, что думаете, что решение hasan - O (N ^ 2), я хотел бы объяснить, почему вы ошибаетесь. Поэтому он предложил:
for (int i=0; i < size; i+=k*2)
for (int j=0; j < k && i+j < size; j++)
arr[i+j] = -arr[i+j];
Число итераций для первого цикла - это size/(k * 2)
а число итераций для второго цикла - k
. Hense, общее число итераций - это size/2
. Который также является числом элементов в массиве, которые необходимо изменить. Вы не можете сделать лучше.