c++ - 反转数字列表并跳过其他数字

Question

给定一个列表和一个数字 k，反转前 k 个元素并保留接下来的 k 个元素。在整个列表中重复此操作。通过反转我的意思是，改变数字的符号。

这是亚马逊的一个面试问题，我在一个网站上遇到过，我试图通过思考如何解决它来解决它，当然我也想知道解决它的最快算法和你的想法。

我想过将数组划分为 K-Steps，然后反转、跳过。然后像合并排序一样合并数组。

Answer 1

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

Answer 2

哈桑解决方案的复杂性：

因为你说你认为哈桑的解决方案是 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. 这也是数组中应该修改的元素数。你不能做得比这更好。