→ CodingMan: 可能每個值用 Set 紀錄一下 加過的值？ 02/12 13:27
推 LPH66: 樓上還是 O(n^2 log n), 因為會插入 Set 的值有 O(n^2) 個 02/12 13:45
→ LPH66: 唔嗯..想了好幾種方法都是 O(n^2 log n) 02/12 13:50
→ pttworld: 找到排序複雜度低於nlogn才有可能。 02/12 13:58
→ pttworld: 另外，隱藏想法錯誤。n^2 + n^2 log(n^2)取後者。 02/12 13:59
→ pttworld: 加號後者過大，前者忽略。也就是主角是排序。 02/12 14:02
隱藏這部份我是想說 造array的時候是否每個element可用O(1)的時間去insert
所以變成只用O(n^2)的時間
推 Sidney0503: 排序低於nlogn就線性排序 02/12 14:45
→ Sidney0503: 但是實際上用起來通常還是quick sort快 02/12 14:45
推 firejox: 如果最大的和跟最小的和差異不大就枚舉之類的 02/12 14:47
推 firejox: 最大的和如果不大 也可以背包 02/12 14:50
謝謝各位的回答 目前看來是無法直接達到目的 感覺f大的方法比較可行些
※ 編輯: Laplace5566 (36.226.198.50), 02/12/2017 15:10:11
→ johnjohnlin: sort 兩個陣列，之後來用 two pointer 可以嗎？ 02/12 17:23
→ johnjohnlin: 應該會變 (nlgn+n*n)，不知道有沒有理解錯誤 02/12 17:24
推 johnjohnlin: 好像複雜度不會變，算了 XD 02/12 17:30