代码之家 › 专栏 › 技术社区 › Esko918

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

little-o big-o objective-c

Esko918 · 技术社区 · 8 年前

我刚从一家公司得到这个面试测试,我轻松地完成了它,但他们说我的功能处于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.

确保每个方法(包括track)在恒定时间内运行(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)中完成这项工作吗。我已经放弃了,所以不要以为你会给我面试的答案。我不打算在那里工作。我只是想看看如何在不遍历数组的情况下解决这个问题。

2 回复 | 直到 8 年前

luk2302 8 年前

我想你一定要写信 trackInt: 以不同的方式:

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

这样,每当添加一个新数字时,您就可以通过一个简单的计算来确定 max (和其他值)在恒定时间内。

实际情况 最大值 方法如下所示:

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

模式、平均值等的增量计算逻辑看起来有点不同,您可能永远不必使用 numbers 虽然是数组,但更可能有 count 和a sum 跟踪。

对于 mode 你可以保留一本地图字典 number 到一个计数器上,该计数器记录该数字出现的频率。此外,您还存储了发生次数最多的当前计数, maxNumberCount . 如果新增加的计数器大于存储的计数器您有一个新的 模式 值,当前 数字 存储/返回和更改 最大数字计数 照着

Sulthan 8 年前

使函数在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 . N计数集 可以使用其他语言中的字典/映射进行模拟(在一般情况下,我们必须使用具有O(1)操作的结构)。唯一的技巧是在添加时执行必要的操作。

还要注意的是,目前这些函数没有遵循Obj-C命名约定,这在面试中也应该很重要。