搜索最近的數字的NSArray

有沒有簡單的方法來搜索NSArray的數字來找到最接近的（或確切的說，如果它存在）匹配用戶輸入的數字？搜索最近的數字的NSArray

說我有這樣一個數組：7, 23, 4, 11, 18, 2，並且用戶輸入5。

程序降序接近度的順序返回三個最近的值：4, 7, 2和最重要給NSArray指數的三個對象：2, 0, 5。

來源

2011-08-25 REDMX

我認爲最簡單的方法是尋找m inimun數字，刪除它，並再次尋找minimun數字等 – TommyG

我開始寫一個for循環，測試每個數字，但我很快意識到，我不能從原始的對象索引陣列。找到這個索引對我的實際程序非常重要 - 我在這裏發佈的是一個簡單的例子，所以我可以學習理論 – REDMX

應該很簡單地追蹤找到的數字的原始索引，但是您可以在沒有修改數組。說你發現最小值，你保持其索引（這是你的第一個數字三），然後，而不是刪除它，你可以用最大數字替換它 - 這樣，你不會改變你的數組.... – TommyG

更新：請參閱下面的比我的第一個更好的解決方案。

下面是使用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; 
}

來源

2011-08-25 20:16:56

這實際上是完美的 - 非常感謝你！我從來沒有想過它自己 – REDMX

國際海事組織，這是沒有必要的字典。ISTM他們是昂貴的矯枉過正。如果你有索引，你會自動獲得索引的數字，所以已經有一個關聯。 –

@Rudy，這是真的。我會盡快更新我的答案。 –

這是一個功課題嗎？一個簡單的方法，利用API來編寫這是生成一個名爲distances從每個原來的號碼包含的距離的數組，創建數組稱爲sorted，然後搜索distances爲最低的三個號碼sorted的排序版本，以獲得從索引您可以查看原始號碼。

來源

2011-08-25 18:31:58

不是家庭作業，太舊了，只是一個新問題。 - 我收集了大部分從以前的研究中寫出的內容，但我無法弄清楚如何從原始數組中獲取索引。我需要在距離中使用鍵/值，其中鍵是距離，而值是數組中的原始索引？或者我錯過了更明顯的東西？ – REDMX

@REDMX：在問題的主體中包含研究摘要或代碼片段（即使它們不起作用）是有幫助的，以便回答者不會重新散列您已知道並且可以給出更有針對性的重點信息。這就是爲什麼我問「到目前爲止你嘗試過什麼？」 –

@REDMX：看到我修改後的答案。我製作了一系列索引，並根據數字到搜索值的距離對其進行排序。該方法返回一個數組，其中包含值的前三個數組。該數組包含3個最近值的**索引**。由於返回的索引（如NSNumbers）直接鏈接到值，因此不需要數組字典或其他字符。 –

樸素方法是將查詢的源陣列，用於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大小，所以它不是一個巨大的空間增長。

來源

2011-08-25 18:33:13 matthias

+ 1，您可能需要使用abs（），以便差異是否爲正值，無論您是否減去更大的值。我假設，如果你動態地做這件事，你不知道是否使用7-5或5-7。 –

起初，我有同樣的想法，但只要你在一個有序數組上操作*和*，你一定要找到比目標數字更大的第一個條目，你總能知道你找到的條目是大於'5'，並且其左邊的條目小於或等於'5'。 – matthias

排序值「間接」的現有陣列，使用索引的陣列，並且由「距離」來搜索值排序。排序後的前三項是「最接近」的值。

例子：

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

來源

2011-08-25 19:32:41

爲什麼你只返回0-3的範圍？（NSMakeRange（0，3）） – zakdances

查看問題。 –

測試的代碼：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

OUTPUT：

個

arrayWithNumbers：（ 7， 23， 4， 11， 18，）

ResultArray是：（ 4， 7，）

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

     )

來源

2011-08-26 09:28:37

搜索最近的數字的NSArray

回答

相關問題