突然看微信公眾號(hào)中iOS Peak雜貨鋪的一篇文章，就“iOS程序員對(duì)算法的要求”，里面有一個(gè)例子：“檢查通訊錄的變化并上傳服務(wù)器”。具體內(nèi)容下圖

但是peak君沒有給出答案，正要項(xiàng)目中也遇到這樣的問題。于是就想怎么解決。

上面代碼的問題是兩層循環(huán)嵌套，這樣時(shí)間復(fù)雜度是O(N^2), 這樣當(dāng)N非常大的時(shí)候，非常可怕。

按照peak的提示，如果我們用哈希表要做，時(shí)間復(fù)雜度會(huì)降低。iOS用哈希表就是字典與Set了。我們這里用字典。先把原來數(shù)組放到字典中，以其中id作為key，內(nèi)容作為value。然后在讓另一個(gè)數(shù)組到字典中查找有沒有這個(gè)key，有這個(gè)key表示在原來數(shù)組中存在，沒有的表示的話原來數(shù)組中沒有這個(gè)key。

具體代碼可以這樣寫

NSMutableDictionary *dic = [NSMutableDictionary dictionary];

?? ?for (Model *content in _dataArray) {

? ? ? ? dic[content.contentId] = content;

? ? }

? ? for (Model *content in array) {

? ? ? ? if (![dic objectForKey:content.contentId]) {

? ? ? ? ? ? [_dataArray addObject:content];

? ? ? ? }

? ? }

這樣雖然還是兩個(gè)循環(huán)，但是不是嵌套了。時(shí)間復(fù)雜度是O(N)+O(N)=O(N)，嗯，最終是O(N)。

算法這個(gè)是一個(gè)程序員的內(nèi)功，平時(shí)都是寫業(yè)務(wù)代碼。想要第一個(gè)方法就寫，以后寫代碼還要想想其他更優(yōu)解。這樣才能成長(zhǎng)更快。