You could build a hash table out of the subviews with each subview's class name as the key.
That's O(n) performance but also O(n) in size.
문제
I have two views V1 and V2 which have n and m subviews respectively. Among the m and n subviews there is a view 'p' which is common.
I am trying to find out this common view 'p' among m and n subviews. Obviously the brute force approach of O(m*n) works fine to get the common view p. But I would like to know if there is a better efficient algorithm that I can use to get that one unique common view which is present in both V1 and V2.
V1 = {B, K, L, P, O, B, C, A, Q, R} V2 = {A, X, W, S, T, K, O};
Running brute-force gives me O as the answer in O(m*n). Here the views O and O have same class. As pointed out in the comments, I am NOT looking for views which have same frame.
Any efficient way to do this?
After some thoughts and also @CrimsonChris answer's, I have the below solution
- (void)commonView:(UIView *)a1 with:(UIView *)a2 {
NSMutableSet *s = [[NSMutableSet alloc] initWithCapacity:[[a1 subviews] count]];
for (UIView *a1SubViews in [a1 subviews]) {
[s addObject:[a1SubViews class]];
}
for (UIView *a2SubView in [a2 subviews]) {
if ([s containsObject:[a2SubView class]]) {
NSLog(@"#Boom, I found the common view %@", a2SubView);
return;
}
}
NSLog(@"NO common subview");
return;
}
But this uses O(n) space, can we optimize it more further?
해결책
You could build a hash table out of the subviews with each subview's class name as the key.
That's O(n) performance but also O(n) in size.
다른 팁
We can do this with O(1) space and O(max(m , n) log m ) time (with m <= n).
If we have two array int[]a and b
with n and m elements:
So at the end, we have a total time complexity is O(max(m , n) log m ) with space is O(1) if you use in-place sorting algorithm (for example: merge - sort).
We can replace int[] a and b
with any Object array, as long as these Object are comparable. (Using hash code is also an option).