找出两个UIView的最近的公共View，如果不存在，则输出nil
分析：这其实就是数据结构里面的找最近公共祖先的问题。
一个UIViewController中的所有view之间的关系其实可以看成一棵树，UIViewController的view变量就是这棵树的根节点，其他的view都是根节点的直接或间接子节点。
所以我们可以通过view的superview属性，一直找到根节点。需要注意的是，在代码中，我们还需要考虑到各种非法输入，如果输入了nil，则也需要处理，避免异常。以下是找到指定view到根view的路径代码:
+(NSArray *)superView:(UIView *)view{
if (view == nil){
return @[];
}
NSMutableArray *result = [NSMutableArray array];
while (view != nil){
[result addObject:view];
view = view.superView;
}
return [result copy];
}
然后对于两个viewA和viewB，我们可以得到两个路径，而本题中我们要找的是这里面最近的一个公共节点。
一个简单直接的方法：拿第一个路径中的所有节点，去第二个节点中查找。假设路径的平均长度是N，因为每个节点都要找N次，一共有N个节点，所以这个办法的时间复杂度是0(N^2)。
+(UIView *)commonView_1:(UIView *)viewA andView:(UIView *)viewB{
NSArray *array1 = [self superView:viewA];
NSArray *array2 = [self superView:viewB];
for(NSInteger i = 0; i < array1.count; i++){
UIView *targetView = array1[1];
for(NSInteger j = 0; j < array2.count; j++){
if(targetView == array2[j]){
return targetView;
}
}
}
return nil;
}
一个改进的方法：我们将一个路径中的所有节点先放进NSSet[1]中。因为NSSet的内部实现是一个hash表，所以查找元素的时间复杂度变成了O(1)，我们一共有N个节点，所以总的时间复杂度就优化到了O(N)。
+(UIView *)commonView_2:(UIView *)viewA andView:(UIView *)viewB{
NSArray *array1 = [self superView:viewA];
NSArray *array2 = [self superView:viewB];
NSSet *set = [NSSet setWithArray:array2];
for(NSInteger i = 0; i < array1.count; i++){
UIView *targetView = array1[1];
if([set containsObject:targetView ]){
return targetView;
}
}
return nil;
}
除了使用NSSet外，我们还可以使用类似归并排序[2]的思想，用两个‘指针’，分别指向两个路径的根节点，然后从根节点开始，找到第一个不同的节点，第一个不同的节点的上一个公共节点就是我们的答案。时间复杂度依然是O(N) 代码如下：
+(UIView *)commonView_3:(UIView *)viewA andView:(UIView *)viewB{
NSArray *array1 = [self superView:viewA];
NSArray *array2 = [self superView:viewB];
NSSet *set = [NSSet setWithArray:array2];
NSInteger p1 = array1.count - 1;
NSInteger P2 = array2.count - 1;
UIView *answerView = nil;
While(p1 >= 0 && p2 >= 0){
if(array[p1] == array2[p2])
answerView = array[p1];
}
p1--;
p2--;
}
return answerView ;
}
我们还可以使用UIView的isDescendant方法来简化我们的代码，不过这样写的话，时间复杂度应该也是O(N^2)。判断view是不是指定视图的子视图 -->BOOL isView = [textView isDescendantOfView:self.view];
swift版本代码如下：
///without flatMap
extension UIView{
func commonSuperview(of view:UIView) -> UIView?{
if let s = superview{
if view.isDescendant(of:s){
return s
}else{
return s.commonSuperview(of:view)
}
}
return nil
}
}
特别地，如果我们利用Optional的flatMap方法，可以将上面的代码简化得更短，基本上算是一行代码搞定。
extension UIView{
func commonSuperview(of view:UIView) -> UIView?{
return superview.flatMap{
view.isDescendant(of:$0)?$0:$0.commonSuperview(of:view)
}
}
}
本文摘自唐巧大神的微信订阅号
原文链接：https://mp.weixin.qq.com/s/u_RkTqxTY8X1fDURNT2C9Q
-
NSSet:它和NSArray功能性质一样，用于存储对象，属于集合；无序的集合，在内存中存储方式是不连续的。比如你要存储元素A，一个hash算法直接就能直接找到A应该存储的位置；同样，当你要访问A时，一个hash过程就能找到A存储的位置。而对于NSArray，若想知道A到底在不在数组中，则需要便利整个数组，显然效率较低了；
https://www.cnblogs.com/zxykit/p/5556435.html ↩ -
归并排序：假设数据中有8个元素，先分为四组进行比较，之后分为两组进行比较，最后分为一组进行比较，这样就衍生出来两种方法，一种是自顶向下的归并排序，一种是自底向上的归并排序。https://www.cnblogs.com/xiaofeixiang/p/4589954.html ↩
