最近，看到这个题目：计算两个UIView最近的公共父类
首先创建4个UIView，分别命名为AView，BView，CView，DView
其中DView继承于BView，BView继承于AView，CView继承与AView
也即
DView--->BView------->AView
CView---->AView
然后我们计算DView和CView最近的公共父类，很明显答案是AView
接下来我们使用程序来实现
通过superClass这个方面可以获得当前类的父类名
比如
Class className = [DView superClass];
获得的就是BView
最初我的解决思路是：
先计算出DView所有的父类，并且将它存进去一个数组
然后计算CView的父类，每次计算出一个父类，就去数组中查找，如果数组中存在这个元素，那么这个类就是我们要找的
如果没有找到，继续调用superClass获得下一个父类，继续寻找
第一种解决办法:时间复杂度O（n2）
首先，定义一个NSMutableArray数组
····
@property (nonatomic, strong) NSMutableArray *DArray;
····
之后懒加载数组
- (NSMutableArray *)DArray {
if (_DArray) {
return _DArray;
}
_DArray = [NSMutableArray array];
return _DArray;
}
- (void)solveMethod1 {
//寻找DView和CView的最近公共父类，一定会存在公共父类的，因为所有的类都继承于基类NSObject，而且DView和CView都属于UIView的子类
Class DSuperClass = [DView superclass];
while (DSuperClass != nil) {
[self.DArray addObject:DSuperClass];
DSuperClass = [DSuperClass superclass];
}
NSLog(@"DView的所有的父类为%@",self.DArray);
Class CSuperClass = [CView superclass];
while (CSuperClass != nil) {
BOOL success = false;
for (int i = 0; i < self.DArray.count; i++) {
if (CSuperClass == [self.DArray objectAtIndex:i]) {
NSLog(@"CView和DView共同的最近父类为%@",CSuperClass);
success = true;
break;
}
}
//当success为true时，说明已经找到相应的父类，跳出循环
if (success) {
break;
}
CSuperClass = [CSuperClass superclass];
}
//这样的话，时间复杂度是O(n2)，需要进行优化
}
这样的话，题目要求虽然是满足了，但是时间复杂度是O（n2）,复杂度太高，需要想办法降低时间复杂度
在简书上看到另外一个作者的解决办法，时间复杂度为O（n），参考链接我放在文末了
第二种解决办法:时间复杂度O（n）
因为UIView的基类都是NSObject，会有一套相同的继承链
每个类的所有父类组成了一个继承链，而在UIKit下，所有的UIView的最终父类也必然是NSObject，其实就相当于这两个类的继承链从NSObject开始向下一直是重合的，直到最后的一个公共父类才开始分开，这个最后的公共父类也是最近的公共父类
接下来，我们分别获取DView和CView的所有父类，存储到DArray和CArray中
代码如下：
- (void)solveMethod2 {
Class CSuperClass = [CView superclass];
while (CSuperClass != nil) {
[self.CArray addObject:CSuperClass];
CSuperClass = [CSuperClass superclass];
}
Class DSuperClass = [DView superclass];
while (DSuperClass != nil) {
[self.DArray addObject:DSuperClass];
DSuperClass = [DSuperClass superclass];
}
NSInteger count = MIN(self.CArray.count, self.DArray.count);
Class resultClass;
for (int i = 0; i < count; i++) {
Class classC = [self.CArray objectAtIndex:self.CArray.count - 1 - i];
Class classD = [self.DArray objectAtIndex:self.DArray.count - 1 - i];
if (classC == classD) {
resultClass = classC;
} else {
break;;
}
}
NSLog(@"最近的公共父类为%@",resultClass);
}
