iT邦幫忙

0

ugly number 解法請益

  • 分享至 

  • xImage

看了很久還是看不懂Method 4(Using Binary Search)的原理是什麼(也可能是我英文太爛?)
有哪位大神可以解釋一下他大概的原理嗎?
https://www.geeksforgeeks.org/ugly-numbers/#:~:text=Ugly%20numbers%20are%20numbers%20whose%20only%20prime%20factors,11%20ugly%20numbers.%20By%20convention%2C%201%20is%20included.

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 個回答

1
海綿寶寶
iT邦大神 1 級 ‧ 2022-03-27 12:17:32
最佳解答

Binary Search 最重要的三個數字就是 left, right 和 mid
原程式加一列後顯示如下
https://ithelp.ithome.com.tw/upload/images/20220327/20001787W8alfhISUy.png

除了原本 Binary Search 的邏輯以外
增加的重點是「計算 left(l) 到 right(r) 之間的 ugly number 個數」(cnt)
1.若 cnt > n(題目), r = mid - 1, ans = mid;, 即找「左邊較小那一半」
2.若 cnt < n, l = mid + 1;, 即找「右邊較大那一半」
最後求得的 ans 即為答案

Jacky115 iT邦新手 4 級 ‧ 2022-03-27 13:48:50 檢舉

謝謝你 大概有看懂它在幹嘛了
但這句「計算 left(l) 到 right(r) 之間的 ugly number 個數」(cnt),我感覺它是「計算 left(l) 到 mid 之間的 ugly number 個數」(cnt),還是我搞錯了

你說的對, 精確地說
1mid 之間的 ugly number 個數

我要發表回答

立即登入回答