Return 在 NSArray 中只出现一次的第一个数字

Question

我想知道这个问题最好或最合适的方法是什么：给定一个数字列表示例 [2, 3, 4, 2, 3]，return 第一个数字只出现曾经在列表中。

我遵循了一些算法方法并想出了这个方法，但不确定 Objective-C 中是否有任何内置的辅助函数可以让我以更好的性能来做到这一点..

如果没有内置解决方案，是否可以对我的方法或任何其他在性能方面可能更好的解决方案进行改进？

这是我为此更新的解决方案：
用于测试：

#import "NSArray+Addons.h"

@implementation ViewController

- (void)viewDidLoad
{
    [super viewDidLoad];

    NSArray<NSNumber *> *array = @[@(2), @(7), @(3), @(2), @(3), @(2), @(7), @(3), @(2), @(3), @(4), @(7), @(5), @(5), @(9)];
    NSLog(@"Unique number: %@", [array firstUniqueNumber]);
}

@end

NSArray 类别：

#import "NSArray+Addons.h"
#import "NSMutableDictionary+Addons.h"

@implementation NSArray (Addons)

- (NSNumber *)firstUniqueNumber
{
    if (!self.count)
    {
        return nil;
    }

    NSMutableDictionary<NSNumber *, NSNumber *> *myUniqueNumbers = [[NSMutableDictionary alloc] init];

    return [myUniqueNumbers uniqueValueFromArray:self];
}

@end

NSMutableDictionary 类别：

#import "NSMutableDictionary+Addons.h"

@implementation NSMutableDictionary (Addons)

- (NSNumber *)uniqueValueFromArray:(NSArray<NSNumber *> *)array
{
    if (!array.count)
    {
        return nil;
    }

    for (NSNumber *number in array)
    {
        if (!self[number])
        {
            self[number] = [NSNumber numberWithInteger:1];
        }
        else
        {
            NSInteger count = [self[number] integerValue];
            count++;
            self[number] = [NSNumber numberWithInteger:count];
        }
    }

    return [self uniqueNumberWithArray:array];
}


- (NSNumber *)uniqueNumberWithArray:(NSArray<NSNumber *> *)array
{
    if (!array.count)
    {
        return nil;
    }

    NSNumber *uniqueNumber = nil;

    for (NSInteger index = array.count - 1; index > 0; index--)
    {
        NSNumber *key = array[index];

        if (self[key] && [self[key] integerValue] == 1)
        {
            uniqueNumber = key;
        }
    }

    return uniqueNumber;
}

@end

Answer 1

这个问题可以简化为element distinctness problem，所以没有线性时间的解决方案，不用散列和额外的space。

平均 O(n) 时间 + space 的一个简单解决方案是：

构建一个基于散列的数据直方图，将每个值映射到它出现的次数。
在直方图中找到数组中第一个值为 1 的数字。

伪代码：

map = new hashmap
for each element x:
   if map contains x is a key:
       map.put(x,map.get(x)+1)
   else:
       map.put(x,1)
for each element x in array:
   if map.get(x) == 1:
       return x
//if reached here - no distinct element

示例：

array = [2, 3, 4, 2, 3]
create histogram: {[2=2] [3=2], [4=1]}
iterate the array:
   check 2, it has value of 2 in histogram. continue
   check 3, it has value of 2 in histogram. continue
   check 4, it has value of 1 in histogram. Return it and finish.

Answer 2

NSCountedSet* set = [[NSCountedSet alloc] initWithArray:array];
NSUInteger index = [array indexOfObjectPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop){
    return [set countForObject:obj] == 1;
}];
return index == NSNotFound ? nil : [array objectAtIndex:index];

Answer 3

-(NSNumber *)returnFirstUniqueFromArray: (NSArray *)array{

    //put the numbers in a set
    NSCountedSet *numbers = [[NSCountedSet alloc] initWithArray:array];
    for(NSNumber *number in array){
        //if it only occurs once return
        if([numbers countForObject:number]==1) return number;
    }

    return nil;

}

这里的关键是您需要一种好方法来跟踪某事发生的次数，因此请利用 NSCountedSet 的 "count" 方法。会告诉你一个对象出现了多少次。

Return 在 NSArray 中只出现一次的第一个数字

Return the first number which occurs only once in an NSArray

algorithm

objective-c

nsarray

ios