新技能
#pragma mark --寻找最近公共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];
}
//然后对于两个ViewA,viewB,我们可以得到两个路径,找到的是最近的一个公共节点。
//一个简单直接的方法:拿第一个路径中的所有节点,去第二个节点中查找。假设路的平均长度是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 *)commomView_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;
}
//除了使用NSSet外,我们还可以使用类似归并排序的思想,用两个指针,分别指向两个路径的根节点,然后从根节点
+ (UIView *)commonView_3:(UIView *)viewA andView:(UIView *)viewB{
NSArray *arr1 = [self superViews:viewA];
NSArray *arr2 = [self superViews:viewB];
NSInteger p1 = arr1.count -1;
NSInteger p2 = arr2.count -1;
UIView *answer = nil;
while (p1>=0&p2>=0) {
if (arr1[p1]==arr2[p2]) {
answer = arr1[p1];
}
p1--;
p2--;
}
return answer;
}