如何在 O(1) 中完成此操作

Question

我刚从一家公司得到这个用于面试测试，我很轻松地完成了它，但他们说我的功能在 o(n) 中。下面是问题

Write a class IntegerTracker with these methods:

track(int) - Receives an integer for tracking. 
get_max() - Returns the max (int) of all integers seen so far. 
get_min() - Returns the min (int) of all integers seen so far. 
get_mean() - Returns the mean (float) of all integers seen so far.
get_mode() - Returns the mode (int) of all integers seen so far.

确保每个方法（包括跟踪）都在恒定时间内运行（O(1) 时间复杂度）。

我是这样完成的

- (instancetype)init{
    if(self == [super init]){
        self.numbers = [[NSMutableArray alloc]init];
    }
    return self;
}

- (void)trackInt:(int)number{
    [self.numbers addObject:[NSNumber numberWithInt:number]];
}

- (int)getMax{

    NSNumber *max = [self.numbers valueForKeyPath:@"@max.self"];
    return [max intValue];
}

- (int)getMin{

    NSNumber *min = [self.numbers valueForKeyPath:@"@min.self"];
    return [min intValue];
}

- (float)getMean{
    NSNumber *average = [self.numbers valueForKeyPath:@"@avg.self"];
    return [average floatValue];
}
- (int)getMode{

    int maxCount = 0;
    int value = 0;
    NSMutableDictionary *mode = [[NSMutableDictionary alloc]init];
    for(NSNumber *n in self.numbers){
        int currentCount = [[mode objectForKey:n.stringValue]intValue];
        currentCount++;
        [mode setObject:@(currentCount) forKey:n.stringValue];
        if(maxCount < currentCount){
            maxCount = currentCount;
            value = [n intValue];
        }
    }

    return value;
}

谁能告诉我应该如何在 O(1) 中完成这个。我已经因为这个而放弃了，所以不要认为你给我面试的答案。我不打算在那里工作。我只是想看看我应该如何在不遍历数组的情况下解决这个问题。

Answer 1

我假设您必须以不同的方式编写 trackInt:：

- (void)trackInt:(int)number{
    if (number > self.max) {
        self.max = number;
    }
    // different logic for the other desired outcomes
}

这样，无论何时添加新数字，您都可以通过简单的计算来确定恒定时间内的 max（和其他值）。

实际的 max 方法如下所示：

- (int) getMax { return self.max; }

mode、avg 等增量计算的逻辑看起来有点不同，尽管您可能永远不必使用 numbers 数组，但更有可能使用 count 和一个 sum 来跟踪。

对于 mode，您可以保留一个字典，将 number 映射到一个计数器，该计数器跟踪该数字出现的频率。此外，您还存储了当前发生次数最多的计数，maxNumberCount。如果新增加的计数器大于存储的计数器你有一个新的mode值，当前number存储/return并改变maxNumberCount相应地。

Answer 2

要使函数在 O(1) 内运行意味着它们内部不能有任何迭代。实际上没有理由实际存储数字。您只需要存储统计信息：

@property (nonatomic) NSInteger min;
@property (nonatomic) NSInteger max;
@property (nonatomic) NSInteger sum;
@property (nonatomic) NSInteger count;

@property (nonatomic) NSCountedSet *numberCounts; // must be initialized in `init`
@property (nonatomic) NSInteger mostFrequentNumber;

- (void)track:(NSInteger)number {
   if (self.count == 0) { 
      self.min = number;
      self.max = number;
      self.sum = number;
      self.count = 1;
      [self.numberCounts addObject:@(number)];
      self.mostFrequentNumber = number;
   } else {
      self.min = MIN(number, self.min);
      self.max = MAX(number, self.max);
      self.sum += number;
      self.count += 1;
      [self.numberCounts addObject:@(number)];
      if ([self.numberCounts countForObject:@(number)] > [self.numberCounts countForObject:@(self.mostFrequentNumber)] {
         self.mostFrequentNumber = number;
      }
   }
}

- (float)getMean {
   if (self.count == 0) { // protection against dividing by zero!
     return 0;
   }

   return ((float) self.sum) / self.count;
}

- (NSInteger)getMode {
   return self.mostFrequentNumber;
}

添加了使用NSCountedSet计算mode的演示。 NSCountedSet 可以使用其他语言中的 dictionary/map 来模拟（在一般情况下，我们必须使用具有 O(1) 操作的结构）。唯一的技巧是在添加时执行必要的操作。

另请注意，目前这些函数不遵循 Obj-C 命名约定，这在面试中也应该很重要。

如何在 O(1) 中完成此操作

How to complete this in O(1)

big-o

objective-c

little-o