数组区间元素取反操作的高效算法优化：寻求低于O(m*n)的方案

思路分析 #

原来的O(m*n)算法每次操作都遍历区间内所有元素，效率低下。我们可以通过统计每个元素的取反次数来优化：取反偶数次等价于没取反，奇数次等价于取反一次。利用差分数组可以在O(1)时间内完成一次区间的取反次数标记，最后通过前缀和计算每个元素的取反次数，再更新原数组，整体时间复杂度为O(m + n)。

具体步骤 #

• 初始化一个长度为数组长度+1的差分数组diff，初始值全为0。
• 遍历每个区间操作[L, R]：
  • 对diff[L]加1，表示从索引L开始，取反次数+1；
  • 对diff[R+1]减1（如果R+1不超过数组长度），表示从索引R+1开始，取反次数-1。
• 计算前缀和得到每个元素的取反次数：
  • 维护一个累计变量count，初始为0；
  • 遍历原数组的每个索引i，将count加上diff[i]；
  • 如果count是奇数，将原数组的array[i]乘以-1；偶数则保持不变。

示例验证 #

以题目中的示例为例：
原数组：[1,-4,-5,2]，操作：[[1,3],[0,1]]

1. 初始化diff = [0,0,0,0,0]
2. 处理第一个操作[1,3]：diff[1] +=1 → diff[1]=1；diff[4] -=1 → diff[4]=-1
3. 处理第二个操作[0,1]：diff[0] +=1 → diff[0]=1；diff[2] -=1 → diff[2]=-1
4. 计算前缀和并更新数组：
   • i=0：count=0+1=1（奇数）→ 1*-1=-1
   • i=1：count=1+1=2（偶数）→ -4不变
   • i=2：count=2-1=1（奇数）→ -5*-1=5
   • i=3：count=1+0=1（奇数）→ 2*-1=-2
     最终结果：[-1,-4,5,-2]，与示例一致。

Java代码实现 #

public class Solution {
    public void updateArray(int[] array, int[][] operations) {
        int n = array.length;
        int[] diff = new int[n + 1]; // 多一位避免R+1越界
        
        for (int[] op : operations) {
            int L = op[0];
            int R = op[1];
            diff[L]++;
            diff[R + 1]--;
        }
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            count += diff[i];
            if (count % 2 != 0) {
                array[i] *= -1;
            }
        }
    }
}

复杂度分析 #

• 时间复杂度：O(m + n)，其中m是操作次数，n是数组长度。遍历操作数组耗时O(m)，遍历原数组计算前缀和并更新耗时O(n)。
• 空间复杂度：O(n)，需要额外的差分数组。

内容的提问来源于stack exchange，提问作者Learner