ugly number 解法請益

ugly number

Jacky115 2022-03-26 22:42:07 ‧ 865 瀏覽

分享至

看了很久還是看不懂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 }} |

直播中

1 個回答

海綿寶寶

iT邦大神 1 級 ‧ 2022-03-27 12:17:32

最佳解答

Binary Search 最重要的三個數字就是 left, right 和 mid
原程式加一列後顯示如下

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