6

我有一个字符串数组，我只想从中提取具有唯一字符集的字符串。（例如，“asdf”和“fdsa”会被认为是多余的）。这是我目前使用的方法：

NSMutableArray *uniqueCharSets = [[NSMutableArray alloc] init];
NSMutableArray *uniqueStrings = [[NSMutableArray alloc] init];        

for (NSString *_string in unique) {
    NSCharacterSet *_charSet = [NSCharacterSet characterSetWithCharactersInString:_string];
    if (![uniqueCharSets containsObject:_charSet]) {
        [uniqueStrings addobject:_string];
        [uniqueCharSets addObject:_charSet];
    }
}

这似乎可行，但它非常缓慢且资源密集。谁能想到更好的方法来做到这一点？

4

3 回答 3

1
  1. 使用 an NSDictionary，将每个字符串的字典排序等价于NSArray输入字符串的 an 映射：（例如adfs=> [afsd, asdf, ...]）
  2. 遍历字典，打印出只有单元素数组值的键（或其值）
于 2012-01-02T01:02:33.927 回答
0

我只是整理了一个简单的例子来说明我将如何处理这个问题，但事实证明它比你最初预期的更奇怪。一方面，NSCharacterSet不实施平等来检查内容。它只使用指针值。基于此，您的示例将无法正常工作。

我的方法是使用 NSSet 为我们处理这些哈希。

@interface StringWrapper : NSObject
@property (nonatomic, copy) NSString *string;
@property (nonatomic, copy) NSData *charSetBitmap;
- (id)initWithString:(NSString*)aString;
@end

@implementation StringWrapper
@synthesize string, charSetBitmap;

- (id)initWithString:(NSString*)aString;
{
    if ((self = [super init]))
    {
        self.string = aString;
    }
    return self;
}

- (void)setString:(NSString *)aString;
{
    string = [aString copy];
    self.charSetBitmap = [[NSCharacterSet characterSetWithCharactersInString:aString] bitmapRepresentation];
}

- (BOOL)isEqual:(id)object;
{
    return [self.charSetBitmap isEqual:[object charSetBitmap]];
}

- (NSUInteger)hash;
{
    return [self.charSetBitmap hash];
}

@end

int main (int argc, const char * argv[])
{
    @autoreleasepool {
        NSMutableSet *stringWrappers = [[NSMutableSet alloc] init];
        NSArray *strings = [NSArray arrayWithObjects:@"abc",@"aaabcccc",@"awea",@"awer",@"abcde", @"ehra", @"QWEQ", @"werawe", nil];
        for (NSString *str in strings)
            [stringWrappers addObject:[[StringWrapper alloc] initWithString:str]];

        NSArray *uniqueStrings = [stringWrappers valueForKey:@"string"];
        NSLog(@"%@", uniqueStrings);

    }
    return 0;
}

代码非常简单。我们创建一个容器对象来缓存字符集位图表示的结果。我们使用位图表示是因为NSData实现isEqual:得当。

于 2012-01-02T00:29:55.657 回答
0

我唯一想到的就是不要使用containsObject: 因为NSMutableArray它不是有序的（通常），我们可以假设它containsObject只是从头开始迭代数组，直到他找到对象。这意味着O(n)（n最坏情况下的比较）。

更好的解决方案可能在于保持数组有序并使用二分法的自定义搜索方法。这样你就会有一个O(log n) 复杂性。
当然，您必须注意保持数组有序（比添加和重新排序更有效），因此您应该使用insertObject:atIndex:方法正确插入元素。

于 2012-01-02T00:39:09.990 回答