如何实现各方法均为O(1)时间复杂度的IntegerTracker类？

哎，真可惜错过了这个机会，但能想着深究优化方案的心态真的很棒！咱们来聊聊怎么把IntegerTracker的所有方法都做到O(1)时间复杂度——核心逻辑其实很简单：不要在查询的时候临时计算结果，而是在每次track整数的时候就同步维护好需要的状态，这样每次调用get方法直接返回预先存好的值就行，完全不用遍历数组。

我们需要给类新增几个实例变量，用来存储每次track时更新好的关键状态：

• maxVal：当前已追踪的最大值
• minVal：当前已追踪的最小值
• sum：所有已追踪数的总和（用long long避免整数溢出）
• count：已追踪数的总个数
• frequencyMap：字典，记录每个整数出现的次数
• modeVal：当前的众数
• modeCount：当前众数的出现次数

下面是改造后的完整代码，每个方法都是O(1)时间复杂度：

@interface IntegerTracker ()
@property (nonatomic, assign) int maxVal;
@property (nonatomic, assign) int minVal;
@property (nonatomic, assign) long long sum;
@property (nonatomic, assign) NSInteger count;
@property (nonatomic, strong) NSMutableDictionary<NSNumber *, NSNumber *> *frequencyMap;
@property (nonatomic, assign) int modeVal;
@property (nonatomic, assign) NSInteger modeCount;
@end

@implementation IntegerTracker

- (instancetype)init {
    self = [super init];
    if (self) {
        // 初始化边界值，确保第一个track的数能正确覆盖
        _minVal = INT_MAX;
        _maxVal = INT_MIN;
        _sum = 0;
        _count = 0;
        _frequencyMap = [[NSMutableDictionary alloc] init];
        _modeVal = 0;
        _modeCount = 0;
    }
    return self;
}

- (void)trackInt:(int)number {
    // 1. 更新总和与数量
    _sum += number;
    _count++;
    
    // 2. 更新最大值
    if (number > _maxVal) {
        _maxVal = number;
    }
    // 3. 更新最小值
    if (number < _minVal) {
        _minVal = number;
    }
    
    // 4. 更新频率字典与众数
    NSNumber *numKey = @(number);
    NSInteger currentFreq = [_frequencyMap[numKey] integerValue];
    currentFreq++;
    _frequencyMap[numKey] = @(currentFreq);
    
    // 如果当前数的出现次数超过当前众数，更新众数
    if (currentFreq > _modeCount) {
        _modeCount = currentFreq;
        _modeVal = number;
    }
    // 补充：如果题目要求多个众数时返回最大/最小值，这里可以加判断
    // 比如：if (currentFreq == _modeCount && number > _modeVal) { _modeVal = number; }
}

- (int)getMax {
    // 处理未追踪任何数的边界情况，这里用断言提示，也可以返回默认值
    NSAssert(_count > 0, @"No numbers have been tracked yet");
    return _maxVal;
}

- (int)getMin {
    NSAssert(_count > 0, @"No numbers have been tracked yet");
    return _minVal;
}

- (float)getMean {
    if (_count == 0) {
        return 0.0f; // 按需求处理空数据场景
    }
    return (float)_sum / _count;
}

- (int)getMode {
    NSAssert(_count > 0, @"No numbers have been tracked yet");
    return _modeVal;
}

@end

1. 溢出问题：用long long存储总和sum，避免多次track大数导致int溢出。
2. 边界初始化：把minVal初始化为INT_MAX，maxVal初始化为INT_MIN，这样第一个track的数肯定会替换这两个值，不用额外判断是否是第一个数。
3. 众数处理：当前代码会保留第一个出现的众数，如果题目要求多个众数时返回最大/最小值，可以在currentFreq == modeCount时添加比较逻辑，按需更新modeVal。
4. 空数据处理：每个get方法都加了空数据判断，用断言或者返回默认值，根据实际业务需求调整即可。

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