將數組中的每個數字添加到數組中的每個其他數字

如何將每個對象（它是一個NSNumber對象）添加到數組中的每個其他NSNumber對象並將總和對象添加到新數組？將數組中的每個數字添加到數組中的每個其他數字

例如

array1 has numbers 1, 2, and 3. 
then do: 
1 + 1 = 2 then add 2 to array2. 
1 + 2 = 3 then add 3 to array2. 
1 + 3 = 5 then add 4 to array2. 

2 + 1 = 3 then add 3 to array2. 
2 + 2 = 4 then add 4 to array2. 
2 + 3 = 5 then add 5 to array2. 

3 + 1 = 4 then add 4 to array2. 
3 + 2 = 5 then add 5 to array2. 
3 + 3 = 6 then add 6 to array2. 

So array2 has 2, 3, 4, 3, 4, 5, 4, 5, 6.

我可以處理刪除重複項。我試過把for循環放在另一個for循環中，這個循環基本上做了我上面概述的內容，但是我有超過28,000個數字，而不是數字1 - 28,000。計算花費了很長時間，因爲有28,000^2可能的總和。當然必須有另一種方式。任何人都可以詳細說明嗎？

來源

2014-02-22 Milo

所以你說你不能有重複？這會對算法產生很大的影響 – Merlevede

@Merlevede對我來說並不重要。重複是可以的，只要不需要三個小時。 – Milo

那你嘗試了什麼？ – Wain

這樣的事情，也許

NSMutableArray *myNewArray = [NSMutableArray array]; 
NSUInteger length = myArray.length; // or size?? I don't remember 
for (NSUinteger i=0; i=0<length; i++) 
    for (NSUinteger j=i; j=0<length; j++) 
     [myNewArray addObject:([array objectAtIndex:i] + [array objectAtIndex:j])];

這裏的祕密是在內部for循環j=i初始狀態。例如，由於您已經完成了1 + 2的總和，因此您不需要再做2 + 1，因此不包括重複項，儘管您仍然可能有重複的結果（例如3 + 4 = 7; 1 + 6 = 7）。

而不是有n^2和，你有n *（n + 1）/ 2和...差不多有一半了！

來源

2014-02-22 08:29:40 Merlevede

謝謝，我現在就試試這個。另外，在你的代碼的最後一行，你的意思是讓'objectAtIndex：i'中的一個成爲'objectAtIndex：j'？順便說一句，這是myArray.count :) – Milo

你是對的，它應該是'j'。 – Merlevede

如果你有一組N個隨機數並且必須將每個數相加，我不能確定它不是O（N²）。

計算所有數字之前導致784.000.000總和之前他們。使用32位整數（不是NSNumber實例對象），內存佔用將近3 GB。

你必須執行這個懶惰（「每筆求和」）

來源

2014-02-22 09:06:37

好點。假設您對連續數字1..100執行此算法。有49個組合，結果= 100。如果結果被添加到字典或刪除重複的集合中，內存的數量可能會大大增加，但是查找時間可能是一個缺點......只是有些過度！ – Merlevede

是的，不同的問題可能有不同的解決方案。「我有超過28,000個數字，不是數字1 - 28,000。」但是，接近1 G計算和對象創建的過程會很緩慢，像「減少一點」這樣明顯的缺陷就不起作用。 –

將數組中的每個數字添加到數組中的每個其他數字

回答

相關問題