如何优化我的代码以将给定索引范围的数组元素与相关元素交换？

Question

考虑具有 N 个元素的整数数组 A，其中每个元素与另一个数组元素具有一对一关系。

对于每个i，其中1≤i≤N在元素i和元素N−i+1之间存在1−>1的关系

任务是对该数组执行如下操作：

给定两个整数 (L,R)，我们必须将该范围内的每个元素与其相关元素交换。（请参阅下面的示例说明）

示例输入

示例输出

5 2 3 4 1

说明对于第一个查询，我们将 1 与 5 交换，2 与 4 交换。现在数组变为 - 5 4 3 2 1

同样，对于第二个查询，我们将 4 与 2 交换，3 与自身交换。所以最后的数组将是 5 2 3 4 1

我的程序是这样的：

import java.util.Scanner;
public class ProfessorAndOps {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    Scanner in=new Scanner(System.in);
    int n=in.nextInt();//length of array
    int a[]=new int[n];//array declaration
    for(int i=0;i<n;i++){
        //inputting array elements
        a[i]=in.nextInt();
    }
    int q=in.nextInt();//number of queries
    for(int i=0;i<q;i++){
        int l=in.nextInt();//left limit
        int r=in.nextInt();//right limit
        //swapping while iterating over the given range of array elements:
        for(int j=l-1;j<=r-1;j++){
            int temp=a[j];
            a[j]=a[n-j-1];
            a[n-j-1]=temp;
            }
        }
    //Printing the output array:
    for(int i=0;i<n;i++){
        if(i!=n-1){
        System.out.print(a[i]+" ");
        }
        else{
            System.out.println(a[i]);
        }

    }

}
}

我只能想出 BruteForce 解决方案。我很确定会有一些预处理步骤或一些带有 l 和 r 变量的优化技术，无论我能想到什么，都会给我错误的答案。请帮我优化这段代码。具体来说，我需要将代码的时间复杂度从 O(N+ Q*(R-L)) 降低到 O(Q+N)

Answer 1

这里有一个O(Q + N)时间，O(N)space算法。想象一下，只有 L 和 R 元素的相应交换计数列表（我们将对 R 计数使用负数）。如果我们在遍历它时维护一个虚拟堆栈怎么办？（"virtual," 我的意思是它不是一个真正的堆栈，只是一个具有某种理论相似性的整数。）

例如：

1  2  3  4  5  6  7  8  9  10

O(Q) processing:

q [1,3]
1  9  8  7  5 ...  <- what would happen to the array
0  1  0 -1  0 <- counts (what we actually store)

q [2,4]
1  9  3  4  6 ...  <- what would happen to the array
0  1  1 -1 -1 <- counts (what we actually store)

O(N) traversal:

index 0 didn't move,                     no change, stack: 0
index 1 moved once,          odd count,  changed,   stack: 1
index 2 moved 2 (stack + 1), even count, no change, stack: 2
index 3 moved 2 (stack),     even count, no change, stack: 2 - 1
index 4 moved 1 (stack),     odd count,  changed,   stack: 1 - 1

如何优化我的代码以将给定索引范围的数组元素与相关元素交换？

How can I optimize my code for Swapping the array elements of given range of indexes with related element?

java

arrays

algorithm

optimization

array-algorithms