今天随机翻开《编程之美》看到2.10这节 按照解法3的思路实现了一下。
- 具体思想：将数组中相邻的两数分在同一组。
- 提升：从扫描一遍数组的比较2N次 降低到比较1.5N次。
- (void)minMaxFinder:(NSArray *)array
{
int max = INT_MIN, min = INT_MAX;
if(!array)
{
NSLog(@"数组为空");
return;
}
if(array.count == 1)
{
NSLog(@"无需比较");
max = min = [[array firstObject] intValue];
}
else
{
for(int i = 1; i < array.count; i += 2) {
int pre = [array[i - 1] intValue];
int suf = [array[i] intValue];
int tempMax = pre > suf ? pre : suf;//找出当前两个元素中大的
int tempMin = pre < suf ? pre : suf;//找出当前两个元素中小的
max = max > tempMax ? max : tempMax;//大的和大的比
min = min < tempMin ? min : tempMin;//小的和小的比
//NSLog(@"current i ：%d",i);
}
if(array.count % 2 != 0) {//如果是奇数在看一下最后一个元素的值
int lastNum = [array.lastObject intValue];
max = max > lastNum ? max : lastNum;
if(max != lastNum) {//如果最大值已经替换成lastNum，min就不需要比较了
min = min < lastNum ? min : lastNum;
}
}
}
NSLog(@"最大%d,最小%d",max, min);
}
测试用例
NSArray *array = @[@(7),@(9),@(1),@(-11),@(6),@(8),@(2)];
结果：最大9,最小-11
有问题请指出 thx.
