求支持动态增删的数字集合最小绝对差值的优化方案

给定一个大小为n的数字集合，以及Q条操作指令，每条指令为向集合中添加或移除一个数字。要求在每条指令执行后，输出当前集合的最小绝对差值。

约束条件 #

• 2 <= N <= 10^6
• 1 <= Q <= 10^6
• -10^9 <= set[i] <= 10^9

示例 #

输入：

set = [2, 4, 7]
ADD 6
REMOVE 7
REMOVE 4
ADD 2

输出：

1
2
4
0

要求使用时间复杂度为**O((N+Q)log(N+Q))**或更优的算法解决。

我当前的实现性能不足，代码如下：

TreeSet<Integer> tree = new TreeSet<>();
HashMap<Integer, Integer> numberFreq = new HashMap<>();

int dupeCount = 0;

for (int i : set) {
    tree.add(i);
    if (numberFreq.get(i) > 0) dupeCount++;
    numberFreq.put(i, numberFreq.getOrDefault(i, 0) + 1);
}

void add(int i) {
    if (numberFreq.get(i) > 0) dupeCount++;
    numberFreq.put(i, numberFreq.getOrDefault(i, 0) + 1);
    tree.add(i); // if duplicate nothing gets added anyway
   
    if (dupeCount > 0) Console.write(0);
    else {
        int smallestBall = tree.first();
        int absDiff;
        int minAbsDiff = Integer.MAX_VALUE;
        while (tree.higher(smallestBall) != null) {
            absDiff = Math.abs(smallestBall - tree.higher(smallestBall));
            minAbsDiff = Math.min(absDiff, minAbsDiff);
            smallestBall = tree.higher(smallestBall);
        }
    Console.write(minAbsDiff);
    }

}

void remove(int i) {
     if (numberFreq.get(i) > 0) dupeCount--;
     else tree.remove(i);
     numberFreq.put(i, numberFreq.get(i) - 1);

     if (dupeCount > 0) Console.write(0);
     else {
         int smallestBall = tree.first();
         int absDiff;
         int minAbsDiff = Integer.MAX_VALUE;
         while (tree.higher(smallestBall) != null) {
             absDiff = Math.abs(smallestBall - tree.higher(smallestBall));
             minAbsDiff = Math.min(absDiff, minAbsDiff);
             smallestBall = tree.higher(smallestBall);
        }
     Console.write(minAbsDiff);
     }
}    

注：原代码remove方法存在逻辑错误：判断numberFreq.get(i) > 0就减少dupeCount不合理，只有当数字频率从2降到1时才需要减dupeCount；另外移除数字时，只有当频率变为0时才需要从TreeSet中删除该数字。

核心问题是每次查询最小差值时遍历整个TreeSet，时间复杂度为O(K)（K为当前不同元素数量），最坏情况下总复杂度会达到O(Q*N)，完全无法应对1e6级别的操作量。

需要通过维护有序差值集合来快速获取最小差值，具体思路：

1. 基础数据结构选型

   • 用TreeSet<Integer>维护当前所有不同数字（保持有序），TreeMap<Integer, Integer>记录每个数字的出现频率。
   • 用TreeMap<Integer, Integer>维护所有相邻数字的差值：键为差值大小，值为该差值出现的次数，通过firstKey()可直接获取当前最小差值。

2. 添加数字的处理逻辑

   • 若数字已存在：
     • 直接增加频率，若之前频率为1，则dupeCount加1，此时最小差值为0，无需处理差值集合。
   • 若数字是新元素：
     • 找到该数字的前驱（lower()）和后继（higher()）。
     • 若前驱存在：计算前驱与当前数字的差值，将其加入差值集合（计数加1）。
     • 若后继存在：计算当前数字与后继的差值，将其加入差值集合（计数加1）。
     • 若前驱和后继都存在：移除原来前驱与后继之间的差值（计数减1，计数为0则删除该键）。
     • 将当前数字加入有序集合，更新频率映射。
     • 若dupeCount为0，最小差值为差值集合的firstKey()。

3. 删除数字的处理逻辑

   • 若删除后数字频率仍大于0：
     • 减少频率，若之前频率为2，则dupeCount减1；若dupeCount仍大于0，最小差值为0，否则取差值集合的firstKey()。
   • 若删除后数字频率变为0：
     • 从有序集合中移除该数字，找到其前驱和后继。
     • 若前驱存在：移除前驱与当前数字的差值（计数减1，计数为0则删除键）。
     • 若后继存在：移除当前数字与后继的差值（计数减1，计数为0则删除键）。
     • 若前驱和后继都存在：计算前驱与后继的新差值，加入差值集合（计数加1）。
     • 删除频率映射中的该数字条目。
     • 若dupeCount为0，最小差值为差值集合的firstKey()。

4. 特殊情况处理

   • 只要dupeCount > 0，说明存在重复数字，最小绝对差值直接为0，无需查询差值集合。

import java.util.TreeMap;
import java.util.TreeSet;

public class MinAbsoluteDifference {
    private TreeSet<Integer> uniqueNumbers;
    private TreeMap<Integer, Integer> freqMap;
    private TreeMap<Integer, Integer> diffCount;
    private int duplicateCount;

    public MinAbsoluteDifference(int[] initialSet) {
        uniqueNumbers = new TreeSet<>();
        freqMap = new TreeMap<>();
        diffCount = new TreeMap<>();
        duplicateCount = 0;

        // 初始化频率和有序集合
        for (int num : initialSet) {
            if (freqMap.containsKey(num)) {
                freqMap.put(num, freqMap.get(num) + 1);
                if (freqMap.get(num) == 2) {
                    duplicateCount++;
                }
            } else {
                freqMap.put(num, 1);
                uniqueNumbers.add(num);
            }
        }

        // 初始化差值集合
        Integer prev = null;
        for (int num : uniqueNumbers) {
            if (prev != null) {
                int diff = num - prev;
                diffCount.put(diff, diffCount.getOrDefault(diff, 0) + 1);
            }
            prev = num;
        }
    }

    public void add(int num) {
        addNum(num);
        System.out.println(duplicateCount > 0 ? 0 : diffCount.firstKey());
    }

    private void addNum(int num) {
        if (freqMap.containsKey(num)) {
            int freq = freqMap.get(num);
            freqMap.put(num, freq + 1);
            if (freq == 1) {
                duplicateCount++;
            }
            return;
        }

        Integer lower = uniqueNumbers.lower(num);
        Integer higher = uniqueNumbers.higher(num);

        // 处理原有相邻差值的移除
        if (lower != null && higher != null) {
            int oldDiff = higher - lower;
            decreaseDiffCount(oldDiff);
        }
        // 添加新的相邻差值
        if (lower != null) {
            int diff = num - lower;
            increaseDiffCount(diff);
        }
        if (higher != null) {
            int diff = higher - num;
            increaseDiffCount(diff);
        }

        uniqueNumbers.add(num);
        freqMap.put(num, 1);
    }

    public void remove(int num) {
        removeNum(num);
        System.out.println(duplicateCount > 0 ? 0 : diffCount.firstKey());
    }

    private void removeNum(int num) {
        int freq = freqMap.get(num);
        if (freq > 1) {
            freqMap.put(num, freq - 1);
            if (freq == 2) {
                duplicateCount--;
            }
            return;
        }

        freqMap.remove(num);
        Integer lower = uniqueNumbers.lower(num);
        Integer higher = uniqueNumbers.higher(num);

        // 移除当前数字相关的差值
        if (lower != null) {
            int diff = num - lower;
            decreaseDiffCount(diff);
        }
        if (higher != null) {
            int diff = higher - num;
            decreaseDiffCount(diff);
        }
        // 添加前驱和后继的新差值
        if (lower != null && higher != null) {
            int newDiff = higher - lower;
            increaseDiffCount(newDiff);
        }

        uniqueNumbers.remove(num);
    }

    private void increaseDiffCount(int diff) {
        diffCount.put(diff, diffCount.getOrDefault(diff, 0) + 1);
    }

    private void decreaseDiffCount(int diff) {
        int count = diffCount.get(diff);
        if (count == 1) {
            diffCount.remove(diff);
        } else {
            diffCount.put(diff, count - 1);
        }
    }

    public static void main(String[] args) {
        int[] initial = {2, 4, 7};
        MinAbsoluteDifference mad = new MinAbsoluteDifference(initial);
        mad.add(6); // 输出1
        mad.remove(7); // 输出2
        mad.remove(4); // 输出4
        mad.add(2); // 输出0
    }
}

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