Re: [理工] 101交大資演

[Aa841018 (andrew)]

※ 引述《howard31622 (howard)》之銘言：
: 題目如下：
: https://imgur.com/oPKojUv
: https://imgur.com/zZvr50v
: 我有先去爬文了
: 我想問的題目有兩大題
: 就麻煩板上的大大替我解釋囉
: 第八題
: 我不知道為什麼我怎麼算都是2
: 第十四大題
: 這大題我實在不太懂意思
: 也是在時間壓力下
: 無法快速審題
: 也請求大大們幫忙囉
不好意思，42題還是看不懂
closet pair，排序花O(nlogn)，排序後的步驟也同樣O(nlogn)，排序與否好像沒有影響
，可是解答是，排序後只要O(logn)？
是我哪裡搞錯了嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.139.64 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1567764304.A.1B5.html
推 Handsomeshen: 跟玩終極密碼一樣，每次都從中間比看比較大還是小，
→ Handsomeshen: 一次就剩一半了。
→ mathtsai: 你沒有看懂題目吧 sorted array
→ mathtsai: 和binary search類似 稍微改變細節而已
→ Aa841018: 不好意思，我實在無法將這題和binary search兜在一起，
→ Aa841018: 可以解釋詳細一點嗎？
→ Aa841018: 要求closet pair應該至少要兩個點吧？那用binary search
→ Aa841018: 怎麼知道找到的那兩個點確實屬於closet pair？亂找不是
→ Aa841018: 很有可能找錯嗎？
→ Ricestone: 42哪裡有寫是closest pair
→ Aa841018: 哦！我懂了！