找出兩個(gè)UIView的最近的公共View，如果不存在，則輸出nil
分析：這其實(shí)就是數(shù)據(jù)結(jié)構(gòu)里面的找最近公共祖先的問(wèn)題。
一個(gè)UIViewController中的所有view之間的關(guān)系其實(shí)可以看成一棵樹(shù)，UIViewController的view變量就是這棵樹(shù)的根節(jié)點(diǎn)，其他的view都是根節(jié)點(diǎn)的直接或間接子節(jié)點(diǎn)。
所以我們可以通過(guò)view的superview屬性，一直找到根節(jié)點(diǎn)。需要注意的是，在代碼中，我們還需要考慮到各種非法輸入，如果輸入了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];
}
然后對(duì)于兩個(gè)viewA和viewB，我們可以得到兩個(gè)路徑，而本題中我們要找的是這里面最近的一個(gè)公共節(jié)點(diǎn)。
一個(gè)簡(jiǎn)單直接的方法：拿第一個(gè)路徑中的所有節(jié)點(diǎn)，去第二個(gè)節(jié)點(diǎn)中查找。假設(shè)路徑的平均長(zhǎng)度是N，因?yàn)槊總€(gè)節(jié)點(diǎn)都要找N次，一共有N個(gè)節(jié)點(diǎn)，所以這個(gè)辦法的時(shí)間復(fù)雜度是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;
}
一個(gè)改進(jìn)的方法：我們將一個(gè)路徑中的所有節(jié)點(diǎn)先放進(jìn)NSSet[1]中。因?yàn)镹SSet的內(nèi)部實(shí)現(xiàn)是一個(gè)hash表，所以查找元素的時(shí)間復(fù)雜度變成了O(1)，我們一共有N個(gè)節(jié)點(diǎn)，所以總的時(shí)間復(fù)雜度就優(yōu)化到了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外，我們還可以使用類(lèi)似歸并排序[2]的思想，用兩個(gè)‘指針’，分別指向兩個(gè)路徑的根節(jié)點(diǎn)，然后從根節(jié)點(diǎn)開(kāi)始，找到第一個(gè)不同的節(jié)點(diǎn)，第一個(gè)不同的節(jié)點(diǎn)的上一個(gè)公共節(jié)點(diǎn)就是我們的答案。時(shí)間復(fù)雜度依然是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方法來(lái)簡(jiǎn)化我們的代碼，不過(guò)這樣寫(xiě)的話，時(shí)間復(fù)雜度應(yīng)該也是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方法，可以將上面的代碼簡(jiǎn)化得更短，基本上算是一行代碼搞定。
extension UIView{
func commonSuperview(of view:UIView) -> UIView?{
return superview.flatMap{
view.isDescendant(of:$0)?$0:$0.commonSuperview(of:view)
}
}
}
本文摘自唐巧大神的微信訂閱號(hào)
原文鏈接：https://mp.weixin.qq.com/s/u_RkTqxTY8X1fDURNT2C9Q
-
NSSet:它和NSArray功能性質(zhì)一樣，用于存儲(chǔ)對(duì)象，屬于集合；無(wú)序的集合，在內(nèi)存中存儲(chǔ)方式是不連續(xù)的。比如你要存儲(chǔ)元素A，一個(gè)hash算法直接就能直接找到A應(yīng)該存儲(chǔ)的位置；同樣，當(dāng)你要訪問(wèn)A時(shí)，一個(gè)hash過(guò)程就能找到A存儲(chǔ)的位置。而對(duì)于NSArray，若想知道A到底在不在數(shù)組中，則需要便利整個(gè)數(shù)組，顯然效率較低了；
https://www.cnblogs.com/zxykit/p/5556435.html ? -
歸并排序：假設(shè)數(shù)據(jù)中有8個(gè)元素，先分為四組進(jìn)行比較，之后分為兩組進(jìn)行比較，最后分為一組進(jìn)行比較，這樣就衍生出來(lái)兩種方法，一種是自頂向下的歸并排序，一種是自底向上的歸并排序。https://www.cnblogs.com/xiaofeixiang/p/4589954.html ?
