在 NSArray 中搜索最近的数字 [英] Searching a NSArray for the nearest number(s)

问题描述

是否有一种简单的方法可以搜索 NSArray 的数字以找到与用户输入的数字最接近的(或精确的，如果存在)匹配?

Is there an easy way to search an NSArray of numbers to find the nearest (or exact if it exists) matches to a user-input number?

假设我有一个这样的数组:7, 23, 4, 11, 18, 2，然后用户输入 5.

Say I have an array like this: 7, 23, 4, 11, 18, 2, and the user enters 5.

程序按接近度降序返回三个最接近的值:4, 7, 2，最重要的是给出了NSArray索引三个对象中的一个:2, 0, 5.

The program returns the three nearest values in descending order of closeness: 4, 7, 2, and most importantly gives the NSArray index of the three objects: 2, 0, 5.

推荐答案

更新:请参阅下文以获得比我的第一个更好的解决方案.

Update: see below for a better solution than my first one.

这是对每个数字及其索引使用 NSDictionary 包装器的解决方案，并使用比较器块进行排序.它可能无法很好地扩展，但可以完成工作.

Here's a solution using NSDictionary wrappers for each number and its index, with sorting using a comparator block. It probably doesn't scale very well, but it gets the job done.

static NSString *const kValueKey = @"value";
static NSString *const kIndexKey = @"index";

+ (void)searchArray:(NSArray *)array forClosestValuesTo:(int)value resultValues:(NSArray **)values resultIndexes:(NSArray **)indexes
{
    NSMutableArray *searchObjs = [NSMutableArray arrayWithCapacity:[array count]];

    [array enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        [searchObjs addObject:[NSDictionary dictionaryWithObjectsAndKeys:obj, kValueKey, [NSNumber numberWithUnsignedInt:idx], kIndexKey, nil]];
    }];

    [searchObjs sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        NSUInteger d1 = ABS([[obj1 objectForKey:kValueKey] intValue] - value);
        NSUInteger d2 = ABS([[obj2 objectForKey:kValueKey] intValue] - value);
        if (d1 == d2) { return NSOrderedSame; }
        if (d1 <  d2) { return NSOrderedAscending; }
        return NSOrderedDescending;
    }];

    NSArray *results = [searchObjs subarrayWithRange:NSMakeRange(0, 3)];

    if (values) {
        *values = [results valueForKey:kValueKey];
    }

    if (indexes) {
        *indexes = [results valueForKey:kIndexKey];
    }
}

更新:这是一个更新的解决方案，它对索引的 C 数组进行排序，消除了对 NSDictionary 包装器的需要

Update: here's an updated solution that sorts a C array of indexes, eliminating the need for NSDictionary wrappers

static NSString *const kValueKey = @"value";
static NSString *const kArrayKey = @"array";

int
CSCompareIndexes(void *data, const void *value1, const void *value2)
{
    NSDictionary *dict = (NSDictionary *)data;

    NSArray *array = [dict objectForKey:kArrayKey];
    int valueToFind = [[dict objectForKey:kValueKey] intValue];

    int index1 = *(int *)value1;
    int index2 = *(int *)value2;

    NSNumber *num1 = [array objectAtIndex:index1];
    NSNumber *num2 = [array objectAtIndex:index2];

    return ABS([num1 intValue] - valueToFind) - ABS([num2 intValue] - valueToFind);
}

void
CSSearchNumberArray(NSArray *array, int valueToFind, NSArray **resultValues, NSArray **resultIndexes)
{
    NSInteger numValues = [array count];

    NSUInteger *indexes = malloc(sizeof(NSUInteger) * numValues);
    assert(indexes);

    int i;
    for (i = 0; i < numValues; i++) {
        indexes[i] = i;
    }

    NSDictionary *data = [NSDictionary dictionaryWithObjectsAndKeys:array, kArrayKey, [NSNumber numberWithInt:valueToFind], kValueKey, nil];
    qsort_r(indexes, numValues, sizeof(NSUInteger), (void *)data, CSCompareIndexes);

    NSMutableArray *tmpValues  = [NSMutableArray arrayWithCapacity:3],
                   *tmpIndexes = [NSMutableArray arrayWithCapacity:3];

    for (i = 0; i < 3; i++) {
        [tmpValues addObject:[array objectAtIndex:indexes[i]]];
        [tmpIndexes addObject:[NSNumber numberWithInt:indexes[i]]];
    }

    if (resultValues) {
        *resultValues = [NSArray arrayWithArray:tmpValues];
    }

    if (resultIndexes) {
        *resultIndexes = [NSArray arrayWithArray:tmpIndexes];
    }

    free(indexes);
}

int main (int argc, char *argv[])
{
    NSAutoreleasePool *pool = [NSAutoreleasePool new];

    NSMutableArray *test = [NSMutableArray array];

    int i;
    for (i = 0; i < 10; i++) {
        [test addObject:[NSNumber numberWithInt:(arc4random() % 100)]];
    }

    NSLog(@"Searching: %@", test);

    NSArray *values, *indexes;
    CSSearchNumberArray(test, 50, &values, &indexes);

    NSLog(@"Values: %@", values);
    NSLog(@"Indexes: %@", indexes);

    [pool drain];
    return 0;
}

这篇关于在 NSArray 中搜索最近的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！