删除有序数组中的重复项。要求空间复杂度O(1),++时间复杂度O(n)
示例+1:
输入:+[1,1,2]
输出:+[1,2]
示例+2:
输入:+[0,0,1,1,1,2,2,3,3,4]
输出:+[0,1,2,3,4]
不啰嗦直接上具体算法代码:
-(NSMutableArray *)cancelRepeatWithArr:(NSMutableArray *)arr { NSLog(@"过滤前 arr:%@",arr); if(arr && [arr isKindOfClass:[NSArray class]] && arr.count > 0) { NSInteger breakValue = 0; NSInteger processCount = 0; while (-1 != breakValue) { BOOL flag = NO; NSInteger i = 0; for(; i < arr.count;i++) { NSInteger sno = [self checkSameValueWithArr:arr number:arr[i] row:i]; if(-1 != sno) { [arr removeObjectAtIndex:sno]; flag = YES; break; } } if(!flag) { breakValue = -1; } } NSLog(@"过滤后 arr:%@",arr); return arr; } else { NSLog(@"过滤前 arr:%@",arr); return nil; } } -(NSInteger)checkSameValueWithArr:(NSMutableArray *)arr number:(NSNumber *)number row:(NSInteger)row { if(!arr || ![arr isKindOfClass:[NSArray class]] || arr.count <= 1) { return -1; } for(NSInteger i = row+1; i < arr.count;i++) { if(number.integerValue == [arr[i] integerValue]) { return i; } } return -1; }
测试代码:
[self cancelRepeatWithArr:[NSMutableArray arrayWithArray:@[@1,@1,@2]]]; [self cancelRepeatWithArr:[NSMutableArray arrayWithArray:@[@0,@0,@1,@01,@1,@01,@2,@2,@3,@3,@4]]];
打印结果:
2021-11-09 16:42:09.452302+0800 LChat_Routes[39682:2272818] [RC:LCChatSessionInputBarControl]pluginItemInfoList count:==============> 0 --TIME:16:42:09.454000+0800【FILE:LCConversationViewController.m--LINE:515】FUNCTION:-[LCConversationViewController cancelRepeatWithArr:] 过滤前 arr:[ 1, 1, 2 ] --TIME:16:42:09.454000+0800【FILE:LCConversationViewController.m--LINE:540】FUNCTION:-[LCConversationViewController cancelRepeatWithArr:] 过滤后 arr:[ 1, 2 ] --TIME:16:42:09.454000+0800【FILE:LCConversationViewController.m--LINE:515】FUNCTION:-[LCConversationViewController cancelRepeatWithArr:] 过滤前 arr:[ 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4 ] --TIME:16:42:09.454000+0800【FILE:LCConversationViewController.m--LINE:540】FUNCTION:-[LCConversationViewController cancelRepeatWithArr:] 过滤后 arr:[ 0, 1, 2, 3, 4 ]