《每周一道算法题》（八）前 K 个高频元素

一 题目

347. 前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

说明：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

二 代码

• 核心代码

- (NSArray *)kFrequentElements:(NSArray<NSNumber *> *)nums k:(NSInteger)k {
    NSMutableDictionary *param = [NSMutableDictionary dictionary];
    
    // 查看出现的次数
    for (NSNumber *number in nums) {
        NSNumber *value = [param objectForKey:number];
        if (value) {
            [param setObject:@([value intValue] + 1) forKey:number];
        } else {
            [param setObject:@(1) forKey:number];
        }
    }
    
    // 对出现的次数进行排序
    NSArray *allTimes = [param.allValues sortedArrayUsingComparator:^NSComparisonResult(NSNumber *obj1, NSNumber *obj2) {
        return [obj1 compare:obj2];
    }];
    
    // 将出现次数进行排序,从大到小排序
    NSMutableArray *sortArrM = [NSMutableArray array];
    for (NSNumber *time in allTimes) {
        [sortArrM insertObject:[NSDictionary dictionaryWithObjectsAndKeys:time,[param allKeysForObject:time].firstObject, nil] atIndex:0];
    }
    
    return sortArrM;
}

• 测试代码

NSArray *nums = @[@1,@1,@1,@2,@2,@3];
NSArray *result = [self kFrequentElements:nums k:2];

for (NSDictionary *dict in result) {
    NSLog(@"%@=%@",dict.allKeys.firstObject,dict.allValues.firstObject);
}

• 运行结果

2019-12-01 17:08:00.398551+0800 08_KFrequentElements[31179:1107468] 1=3
2019-12-01 17:08:00.398728+0800 08_KFrequentElements[31179:1107468] 2=2
2019-12-01 17:08:00.398838+0800 08_KFrequentElements[31179:1107468] 3=1

项目链接地址- 08_KFrequentElements

每周一道算法题 - 笔记