2

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

使用这些方法编写一个类 IntegerTracker：

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) 中完成这个。我已经为此放弃了，所以不要以为你给我面试的答案。我不打算在那里工作。我只想看看我应该如何在不遍历数组的情况下解决这个问题。

4

2 回答 2

6

我假设您必须以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; }

模式、平均值等增量计算的逻辑看起来有点不同，尽管您可能永远不必使用numbers数组，但更有可能有 acount和 asum来跟踪。

因为mode您可以保留一个映射number到一个计数器的字典，该计数器跟踪该数字出现的频率。此外，您存储当前出现次数最多的数字，maxNumberCount. 如果 新增加的计数器大于存储的计数器，则您有一个新mode值，当前number存储/返回并maxNumberCount相应更改。

于 2018-01-05T16:03:32.570 回答
4

使函数在 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;
}

添加了mode使用NSCountedSet. NSCountedSet可以使用其他语言的字典/映射来模拟（在平均情况下，我们必须使用具有 O(1) 操作的结构）。唯一的技巧是在添加时执行必要的操作。

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

于 2018-01-05T16:08:35.487 回答