一.序言

最近一直在面试也没怎么上传技术文章了, 今天心血来潮写一写面试的经历吧.

二.面试题

面试题是怎么从一个无序的集合中找出第k大的数字, 很简单的一道题到当时并没有第一刻想到排序而是想到了遍历一下把数值建立成键值对, 从一定程度来说我是自己用了方法实现排序, 下面直接上我的代码

- (void)viewDidLoad {
    [super viewDidLoad];
    
    // 第K大的数字
    NSInteger i = 1;
    NSLog(@"第%ld大的数字是%ld", i, [self getNumberForK:i]);
}

// 获取第K大的数字
- (NSInteger)getNumberForK:(NSInteger)k {
    // 创建无序集合
    NSSet *set = [NSSet setWithArray:@[@(2), @(1), @(4), @(3), @(100)]];
    NSArray *arr = set.allObjects;
    NSMutableArray *marr = arr.mutableCopy;
    NSMutableDictionary *mdic = @{}.mutableCopy;
    // 循环遍历数组 - 注意这里为什么要把原数组复制一份 因为循环中的数组不可删除元素
    for (NSInteger i = 1; i <= arr.count; i++) {
        // 找到最大值
        NSNumber *maxNumber = [self maxNumber:marr];
        // 移除最大值
        [marr removeObject:maxNumber];
        // 把最大值存储为键值对
        [mdic setObject:maxNumber forKey:@(i)];
    }
    NSLog(@"字典结构是 %@", mdic);
    return [[mdic objectForKey:@(k)] integerValue];
}

- (NSNumber *)maxNumber:(NSArray *)arr {
    NSInteger maxNumber = 0;
    // 设置只赋值一次
    BOOL flag = NO;
    for (NSNumber *number in arr) {
        if (!flag) {
            maxNumber = number.integerValue;
            flag = YES;
        }
        NSInteger num = number.integerValue;
        if (maxNumber < num) {
            maxNumber = num;
        }
    }
    return @(maxNumber);
}

思路很简单 找到最大值然后移除最大值后再次寻找最大值 直到把所有的数字都舔一遍并把他们记录在字典中

2020-03-24 17:03:34.145579+0800 paixu[69093:1011228] 字典结构是 {
    3 = 2;
    2 = 3;
    1 = 4;
    4 = 1;
}
2020-03-24 17:03:34.145673+0800 paixu[69093:1011228] 第1大的数字是4
2020-03-24 17:03:34.178196+0800 paixu[69093:1011228] Metal API Validation Enabled

因为字典是无序的这里看起来比较奇怪 但不影响它的效果 我们可以看到

1 对应 4
2 对应 3
3 对应 2
4 对应 1

运行结果一目了然 程序显然是正确的 但我们有没有更好的方法呢 下面我们来实现一下冒泡排序

冒泡排序很显然 我已经忘得差不多了 那么我们就从冒泡排序的原理与双循环入手

首先冒泡排序的原理 就是用前一个元素比上后一个元素 如果前一个小于后一个 那么就把他们互换位置 那么有了思路 我们就可以写了

假如排序之前是 3 2 1 4
第一轮 3 2 1 4 / 3 2 1 4 / 3 2 4 1
第二轮 3 2 4 1 / 3 4 2 1
第三轮 4 3 2 1

一共需要三轮 每一轮的次数依次减1 因为最后一个数永远是最小的

NSSet *set = [NSSet setWithArray:@[@(2), @(1), @(4), @(3)]];
    NSMutableArray *arr = set.allObjects.mutableCopy;
    NSInteger count = arr.count;
    for (NSInteger i = 0; i < count - 1; i++) {
        for (NSInteger j = 0; j < count - 1 - i; j++) {
            NSInteger num1 = [arr[j] integerValue];
            NSInteger num2 = [arr[j + 1] integerValue];
            if (num1 < num2) {
                NSInteger temp = num1;
                arr[j] = @(num2);
                arr[j + 1] = @(temp);
            }
        }
    }
    
    NSLog(@"%@", arr);

然后我们来看看它的时间复杂度
先看百度的定义

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

1.算法的时间复杂度是个函数
2.时间复杂度用来表示算法的运行时间
3.时间复杂度用大写的O来表示

最终答案 冒泡排序的时间复杂度为 O(n²)