Tìm kiếm một NSArray cho (các) số gần nhất

Question

Có cách nào dễ dàng để tìm kiếm số NSArray để tìm gần nhất (hoặc chính xác nếu nó tồn tại) khớp với số người dùng nhập không?

Giả sử tôi có một mảng như sau: 7, 23, 4, 11, 18, 2 và người dùng nhập 5. chương trình

trả về ba giá trị gần nhất trong thứ tự của sự gần gũi tự giảm dần: 4, 7, 2, và quan trọng nhất là cung cấp cho các chỉ số NSArray trong ba đối tượng: 2, 0, 5.

Answer 1

Cập nhật: xem dưới đây để biết một giải pháp tốt hơn so với một đầu tiên của tôi.

Đây là giải pháp sử dụng trình bao bọc NSDictionary cho mỗi số và chỉ mục của nó, với phân loại bằng khối so sánh. Nó có thể không quy mô rất tốt, nhưng nó được thực hiện công việc.

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ập nhật: đây là một giải pháp cập nhật mà sắp xếp một mảng C các chỉ số, loại bỏ sự cần thiết của giấy gói 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

Đây có phải là câu hỏi về bài tập về nhà không? Một cách dễ dàng để mã hóa điều này bằng cách sử dụng apis là tạo một mảng gọi là distances chứa khoảng cách từ mỗi số gốc, tạo một phiên bản được sắp xếp của mảng đó được gọi là sorted, sau đó tìm kiếm distances cho ba số thấp nhất trong sorted để lấy chỉ mục từ bạn có thể tra cứu số gốc.

Answer 3

Phương pháp ngây thơ sẽ được tìm kiếm trên mảng nguồn cho 5, làm tăng số lần phát hiện và lưu trữ các thông tin thích hợp nếu tìm thấy, sau đó tìm kiếm 4 và 6 vv

Một phương pháp thứ hai sẽ được giữ một sắp xếp bản sao của mảng nguồn: 2, 4, 7, 11, 18, 23

sau đó sử dụng -indexOfObjectPassingTest: để tìm ra số đầu tiên lớn hơn 5 trong mảng đó, sau đó so sánh con số đó với hàng xóm trái của nó, để xem đó là gần gũi hơn với 5:

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

Nếu người hàng xóm bên trái thắng, lưu trữ thông tin của nó, sau đó so sánh hàng xóm trái của nó với bản gốc hơn hơn lăm số:

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

Nhưng nếu phía bên phải thắng, so sánh người hàng xóm phù hợp với người thua cuộc:

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

Bạn chỉ cần thực hiện ba so sánh trong trường hợp này và bạn cần phải quyết định xem bạn có muốn sử dụng < hoặc <= hay không. Mảng thứ hai của bạn chỉ là kích thước n * ptr, vì vậy nó không phải là một sự tăng trưởng không gian lớn.

Answer 4

Sắp xếp mảng giá trị hiện tại "gián tiếp", sử dụng một loạt chỉ mục và sắp xếp theo "khoảng cách" cho giá trị tìm kiếm. Ba mục đầu tiên sau khi sắp xếp là các giá trị "gần nhất".

Ví dụ:

#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 5

Tested Mã số: 100% các công trình

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 

OUTPUT:

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

ResultArray là: ( 4, 7,)

indexArray là: (

"<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)]" 

     )