iOS 面试题（一）：寻找最近公共 View --转自唐巧

题目：找出两个 UIView 的最近的公共 View，如果不存在，则输出 nil 。
分析：这其实是数据结构里面的找最近公共祖先的问题。
一个 UIViewController 中的所有 view 之间的关系其实可以看成一颗树，UIViewController 的 view 变量是这颗树的根节点，其它的 view 都是根节点的直接或间接子节点。
所以我们可以通过 view 的 superview 属性，一直找到根节点。需要注意的是，在代码中，我们还需要考虑各种非法输入，如果输入了 nil，则也需要处理，避免异常。以下是找到指定 view 到根 view 的路径代码：

• (NSArray *)superViews:(UIView *)view {
  if (view == nil) {
  return @[];
  }
  NSMutableArray *result = [NSMutableArray array];
  while (view != nil) {
  [result addObject:view];
  view = view.superview;
  }
  return [result copy];
  }

然后对于两个 view A 和 view B，我们可以得到两个路径，而本题中我们要找的是这里面最近的一个公共节点。
一个简单直接的办法：拿第一个路径中的所有节点，去第二个节点中查找。假设路径的平均长度是 N，因为每个节点都要找 N 次，一共有 N 个节点，所以这个办法的时间复杂度是 O（N^2）。

• (UIView *)commonView_1:(UIView *)viewA andView:(UIView *)viewB {
  NSArray *arr1 = [self superViews:viewA];
  NSArray *arr2 = [self superViews:viewB];
  for (NSUInteger i = 0; i < arr1.count; ++i) {
  UIView *targetView = arr1[i];
  for (NSUInteger j = 0; j < arr2.count; ++j) {
  if (targetView == arr2[j]) {
  return targetView;
  }
  }
  }
  return nil;
  }

一个改进的办法：我们将一个路径中的所有点先放进 NSSet 中。因为 NSSet 的内部实现是一个 hash 表，所以查找元素的时间复杂度变成了 O（1），我们一共有 N 个节点，所以总时间复杂度优化到了 O（N）。

• (UIView *)commonView_2:(UIView *)viewA andView:(UIView *)viewB {
  NSArray *arr1 = [self superViews:viewA];
  NSArray *arr2 = [self superViews:viewB];
  NSSet *set = [NSSet setWithArray:arr2];
  for (NSUInteger i = 0; i < arr1.count; ++i) {
  UIView *targetView = arr1[i];
  if ([set containsObject:targetView]) {
  return targetView;
  }
  }
  return nil;
  }