Поиск NSArray для ближайшего номера (ов)

Question

Есть ли простой способ поиска NSArray чисел, чтобы найти ближайшие (или точные, если они существуют) совпадения с введенным пользователем номером?

Скажем, у меня есть такой массив: 7, 23, 4, 11, 18, 2, и пользователь вводит 5.

Программа возвращает три ближайших значения в порядке убывания близости: 4, 7, 2, а наиболее важно дает индекс NSArrayтри объекта: 2, 0, 5.

Answer 1

Обновление: см. Ниже для лучшего решения, чем мой первый.

Вот решение, использующее оболочки NSDictionary для каждого числа и его индекса, с сортировкой с использованием блока компаратора. Вероятно, он не очень хорошо масштабируется, но он выполняет свою работу.

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

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;
}

Answer 2

Сортировка существующего массива значений «косвенно» с использованием массива индексов и сортировка по «расстоянию» до искомого значения. Первые три элемента после сортировки являются «ближайшими» значениями.

Пример:

#import <Foundation/Foundation.h>

@interface NearestSearcher : NSObject { }
+ (NSArray *) searchNearestValuesOf: (int) value inArray: (NSArray *) values;
@end

@implementation NearestSearcher

+ (NSArray *) searchNearestValuesOf: (int) value inArray: (NSArray *) values
{
    // set up values for indexes array
    NSMutableArray *indexes = [NSMutableArray arrayWithCapacity: values.count];
    for (int i = 0; i < values.count; i++)
        [indexes addObject: [NSNumber numberWithInt: i]];

    // sort indexes 
    [indexes sortUsingComparator: ^NSComparisonResult(id obj1, id obj2) 
     {
         int num1 = abs([[values objectAtIndex: [obj1 intValue]] intValue] - value);
         int num2 = abs([[values objectAtIndex: [obj2 intValue]] intValue] - value);

         return (num1 < num2) ? NSOrderedAscending : 
                (num1 > num2) ? NSOrderedDescending : 
                                NSOrderedSame;
     }];

    return [indexes subarrayWithRange: NSMakeRange(0, 3)];
}
@end


// DEMO

#define NUM_VALUES 20

int main (int argc, const char * argv[])
{

    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

    // DEMO SETUP

    // set up values array with random values
    NSMutableArray *values = [NSMutableArray arrayWithCapacity: NUM_VALUES];
    for (int i = 0; i < NUM_VALUES; i++)
        [values addObject: [NSNumber numberWithInt: arc4random() % 200]];

    // display values array
    for (int i = 0; i < values.count; i++)
        NSLog(@"%2d: %4d", i, [[values objectAtIndex: i] intValue]);

    // get a random value for x
    int x = arc4random() % 200;

    // METHOD INVOCATION

    NSArray *results = [NearestSearcher searchNearestValuesOf: x inArray: values];

    // SHOW RESULTS

    NSLog(@"------------------------");

    NSLog(@"x: %d", x);
    for (NSNumber *num in results)
        NSLog(@"%@: %@", num, [values objectAtIndex: [num intValue]]);

    [pool drain];
    return 0;
}

Answer 3

Наивным методом будет поиск в исходном массиве 5, увеличение найденного счетчика и сохранение соответствующей информации, если она найдена, затем поиск 4 и 6 и т. Д.

Второй способ - сохранить отсортированную копию исходного массива: 2, 4, 7, 11, 18, 23

затем используйте -indexOfObjectPassingTest:, чтобы найти первое число больше 5 в этом массиве, затем сравните это число с его левым соседом, чтобы увидеть, какое из них ближе к 5:

(7-5) < (5-4) ? storeinfo(7) : storeinfo(4)

Если победит левый сосед, сохраните его информацию, затем сравните его левый сосед с исходным числом больше пяти:

(7-5) < (5-2) ? storeinfo(7) : storeinfo(2)

Но если победит правая сторона, сравните ее правого соседа с проигравшим:

(11-5) < (5-2) ? storeinfo(11) : storeinfo(2)

В этом случае вам нужно всего лишь сделать три сравнения, и вам нужно решить, хотите ли вы использовать < или <=. Ваш второй массив имеет размер n * ptr, так что это не огромный рост пространства.

Answer 4

Протестированный код: 100% работает

NSMutableArray *arrayWithNumbers=[[NSMutableArray alloc]initWithObjects:[NSNumber numberWithInt:7],[NSNumber numberWithInt:23],[NSNumber numberWithInt:4],[NSNumber numberWithInt:11],[NSNumber numberWithInt:18],[NSNumber numberWithInt:2],nil];

NSLog(@"arrayWithNumbers : %@ \n\n",arrayWithNumbers);





NSMutableArray *ResultArray = [ [ NSMutableArray alloc] init];

NSMutableArray *lowestArray = [ [ NSMutableArray alloc] init];

NSMutableArray *tempArray = [ [ NSMutableArray alloc] init];

NSMutableArray *indexArray = [ [ NSMutableArray alloc] init];


NSNumber *numberToFind=[NSNumber numberWithInt:5];

int limitToFilter = 3;


    for (NSNumber *number in arrayWithNumbers) {

        int a=[number intValue]-[numberToFind intValue];

        [lowestArray addObject:[NSNumber numberWithInt:abs(a)]];


    }

tempArray=[lowestArray mutableCopy];

NSSortDescriptor *LowestTohighest = [NSSortDescriptor sortDescriptorWithKey:@"self" ascending:YES];

[lowestArray sortUsingDescriptors:[NSArray arrayWithObject:LowestTohighest]];

int upto = limitToFilter-[ResultArray count];

for (int i = 0; i < upto; i++) {


    [lowestArray objectAtIndex:i];

    if ([tempArray containsObject:[lowestArray objectAtIndex:i]]) {


        NSUInteger index=[tempArray indexOfObject:[lowestArray objectAtIndex:i]];



        [ResultArray addObject:[arrayWithNumbers objectAtIndex:index]];


        [indexArray addObject:[NSIndexSet indexSetWithIndex:index]];



    }

}

NSLog(@"ResultArray is : %@ \n\n",ResultArray);

NSLog(@"indexArray is : %@ \n\n",indexArray);


    //here release all 4 arrays if u dont need them

ВЫХОД:

arrayWithNumbers: (7, 23, 4, 11, 18, 2)

ResultArray - это: (4, 7, 2)

indexArray - это: (

    "<NSIndexSet: 0x4e06620>[number of indexes: 1 (in 1 ranges), indexes: (2)]",

    "<NSIndexSet: 0x4e04030>[number of indexes: 1 (in 1 ranges), indexes: (0)]",

    "<NSIndexSet: 0x4e06280>[number of indexes: 1 (in 1 ranges), indexes: (5)]"

        ) 

Answer 5

Это домашнее задание?Простой способ закодировать это с помощью apis - сгенерировать массив с именем distances, содержащий расстояние от каждого исходного числа, создать отсортированную версию этого массива с именем sorted, а затем выполнить поиск distances для наименьших трех чисел вsorted чтобы получить индекс, из которого вы можете найти исходное число.