[討論] 陣列搜尋問題

[VastThunder (↑↑↓↓←→←→)]

假設今天給定一串整數陣列
內含數個不相等的數值
給定一個目標區間 假設0~500好了
印出不包含於陣列內容的數值

如何讓整體 CPU calculation、Memory allocation 消耗最少？
沒有想到一個好的演算法...

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.58.160.1
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1434540498.A.68E.html
※ 編輯: VastThunder (61.58.160.1), 06/17/2015 19:28:45
→ CaptainH: 可以先sort嗎?
推 johnjohnlin: 感覺不用 sort?
→ johnhmj: 時間不考慮嗎？
→ VastThunder: 我也是覺得不需要sort
→ VastThunder: array={1,44,55,100,105,106,201,254,305,339,380}
→ uranusjr: 「整體 CPU calculation、Memory allocation 消耗最少」
→ uranusjr: 你要先定義這個需求, 不可能同時最佳化兩者
→ Hazukashiine: 看情況，但是大多不用 sort 會比較符合你的需求
→ MOONRAKER: 0-500隨便寫就好了 5e+06還差不多
→ MOONRAKER: 你給的陣列剛好就是sort好的當然馬不用sort
推 EdisonX: 兩個 loop 做 xor
→ EdisonX: for(i=0;i<=500;++i) msk^=i;
→ EdisonX: for(i=0;i<500;++i) msk^=ary[i];  最後 msk 就是少的數.
→ EdisonX: 啊！我漏了！少的數可能不只一個... 那就用 bitwise 吧
→ EdisonX: 出現過的設 n-bit 為 1, 最後 polling 哪些 bit 為 0
→ anyoiuo: 這樣? https://ideone.com/qqLwng