1.现有两个无序数组a和b,b中的元素在a中都存在,请设计一个方案,找出在a中,但不在b中的所有元素.请考虑降低时间复杂度.
方法1: //首先呢,前看看苹果是否提供这类的比较方法
很幸运,苹果提供了 NSPredicate,它所属Cocoa框架.利用它可以做类似数据库那样的查询 筛选等..
注：NSPredicate所属Cocoa框架,在密码、用户名等正则判断中经常用到.
类似于SQL语句
NOT 不是
SELF 代表字符串本身
IN 范围运算符
那么NOT (SELF IN %@) 意思就是：不是这里所指定的字符串的值
实验代码:
NSArray *aArray = [[NSArray alloc] initWithObjects:@”0”,@”8”,@”9”,@”2”,@”1”,@”5”,nil];
NSArray *bArray = [[NSArray alloc] initWithObjects:@"2",@"0",@"1",@"5",nil];
NSPredicate * filterPredicate = [NSPredicate predicateWithFormat:@"NOT (SELF IN %@)",bArray];
//过滤数组
NSArray * reslutFilteredArray = [aArray filteredArrayUsingPredicate:filterPredicate];
NSLog(@"Reslut Filtered Array = %@“,reslutFilteredArray);
思考 苹果这样做 时间和复杂程度有哪些好处？
方法2:通过遍历(1)
NSMutableArray reslutArr = [[NSMutableArray alloc] initWithArray:aArray];
for(int i = 0 ; i < aArray.count; i++)
{
NSString aStr = aArray[i];
NSLog(@”aStr:%@”,aStr);
for (int j = 0; j< bArray.count; j++) {
NSString *bStr = bArray[j];
if([aStr isEqualToString:bStr])
{
NSLog(@”%@”,bStr);
[reslutArr removeObject:aStr];
break;
}
}
}
NSLog(@“reslutArr:%@“,reslutArr);
//遍历(2) 对1的优化. 从后往前遍历数组,然后匹配删除.使用containsObject方法的场景很常见,例如:判断某一个元素(对象)是否存在数组中.
int i = (int)[aArray count]-1;
for(;i >= 0;i –){
//containsObject 判断元素是否存在于数组中(根据两者的内存地址判断,相同：YES 不同：NO）
if([bArray containsObject:[aArray objectAtIndex:i]]) {
[aArray removeObjectAtIndex:i];
}
}
NSLog(@”Data Array = %@“,aArray);
//这里的aArray修改成了可变数组 方便removeObject不用定义第三个数组
/ 遍历(3) 通过字典key 来进行对另一个数组的remove
时间复杂度为n,一重For循环B数组 考虑b数组比a数组大,换成循环a数组 先将a数组转换成字典,所有元素作为Key 然后遍历B数组,B.元素作为Key到a字典去取值 这样时间复杂度为2n 我说的是纯算法,与具体编程语言无关
/
NSMutableDictionary dic = [[NSMutableDictionary alloc] init];
for (int i = 0 ;i< aArray.count ; i ++)
{
NSString aKey = aArray[i];
[dic setValue:@”1” forKey:aKey];
}
NSLog(@”dic:%@”,dic);
for (int j = 0; j < bArray.count; j++) {
NSString *bKey = bArray[j];
[dic removeObjectForKey:bKey];
NSLog(@"dic.allKeys:%@",dic.allKeys);
}
//思考比较这几种的 时间复杂度,比较下哪个最优？
测试两段代码运行速度
http://www.cocoachina.com/ios/20100721/1901.html
我打印了下时间 ,通过遍历和方法1 用了 ：
谓词和遍历 2016-03-06 11:45:23.717 TestAB[1000:69199] >>>>>>>>>>cost time = 0.000007
通过字典这种方法用了 2016-03-06 11:46:47.528 TestAB[1036:71234] >>>>>>>>>>cost time = 0.000011
也就是说 最好还是用系统自带的谓词或者用自己写的遍历会计算机处理会快一些.当然字典这种也是简便清晰快捷的方法.
具体代码请看我的github地址:https://github.com/jiecoding/ABArrayAlgorithm