看了很久還是看不懂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.
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 即為答案