[討論] 陣列搜尋問題

看板C_and_CPP作者 (↑↑↓↓←→←→)時間9年前 (2015/06/17 19:28), 9年前編輯推噓2(2推 0噓 14→)
留言16則, 9人參與, 最新討論串1/1
假設今天給定一串整數陣列 內含數個不相等的數值 給定一個目標區間 假設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
→
06/17 19:35, , 1F
可以先sort嗎?
06/17 19:35, 1F
推
06/17 20:21, , 2F
感覺不用 sort?
06/17 20:21, 2F
→
06/17 20:40, , 3F
時間不考慮嗎？
06/17 20:40, 3F
→
06/17 21:03, , 4F
我也是覺得不需要sort
06/17 21:03, 4F
→
06/17 21:04, , 5F
array={1,44,55,100,105,106,201,254,305,339,380}
06/17 21:04, 5F
→
06/17 21:07, , 6F
「整體 CPU calculation、Memory allocation 消耗最少」
06/17 21:07, 6F
→
06/17 21:07, , 7F
你要先定義這個需求, 不可能同時最佳化兩者
06/17 21:07, 7F
→
06/17 21:14, , 8F
看情況，但是大多不用 sort 會比較符合你的需求
06/17 21:14, 8F
→
06/17 21:15, , 9F
0-500隨便寫就好了 5e+06還差不多
06/17 21:15, 9F
→
06/17 21:16, , 10F
你給的陣列剛好就是sort好的當然馬不用sort
06/17 21:16, 10F
推
06/18 00:49, , 11F
兩個 loop 做 xor
06/18 00:49, 11F
→
06/18 00:50, , 12F
for(i=0;i<=500;++i) msk^=i;
06/18 00:50, 12F
→
06/18 00:51, , 13F
for(i=0;i<500;++i) msk^=ary[i]; 最後 msk 就是少的數.
06/18 00:51, 13F
→
06/18 00:52, , 14F
啊！我漏了！少的數可能不只一個... 那就用 bitwise 吧
06/18 00:52, 14F
→
06/18 00:53, , 15F
出現過的設 n-bit 為 1, 最後 polling 哪些 bit 為 0
06/18 00:53, 15F
→
06/18 13:31, , 16F
06/18 13:31, 16F
‣ 更多 VastThunder 的文章
文章代碼(AID): #1LWLdIQE (C_and_CPP)