找出两个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

---

1. NSSet:它和NSArray功能性质一样，用于存储对象，属于集合；无序的集合，在内存中存储方式是不连续的。比如你要存储元素A，一个hash算法直接就能直接找到A应该存储的位置；同样，当你要访问A时，一个hash过程就能找到A存储的位置。而对于NSArray，若想知道A到底在不在数组中，则需要便利整个数组，显然效率较低了；
   https://www.cnblogs.com/zxykit/p/5556435.html ↩

2. 归并排序：假设数据中有8个元素，先分为四组进行比较，之后分为两组进行比较，最后分为一组进行比较，这样就衍生出来两种方法，一种是自顶向下的归并排序，一种是自底向上的归并排序。https://www.cnblogs.com/xiaofeixiang/p/4589954.html ↩