如何在O(1)中完成此

Question

我刚刚从一家公司接受了面试测试,我轻松地完成了它,但他们说我的功能是在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)中完成这个.我已经放弃了原因,所以不要认为你给我一个面试的答案.我不打算在那里工作.我只是想知道如何在不迭代数组的情况下解决这个问题.

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; }

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

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