Java Solution by Binary Search


  • 0
    W

    use an array to hold the ugly numbers, suppose at ith position and the current number is x; so the next number must be some number, say y, which is less than x, but 2 * y or 3 * y or 5 *y just greater than x;
    The difficulty here is how to find the y; if just go through from 0/1 to i, the algorithm will end up O(n * n); I just noticed that the numbers before i is actually sorted. so I can use binary search, the search target is actually x / 2, x / 3 and x / 5;

    following is the code:

    public int nthUglyNumber(int n) {
        if (n <= 5) {
            return n;
        }
        int[] zs = {2, 3, 5};
        int[] nums = new int[n + 1];
        int i = 1;
        for (; i <= 5; i++) {
            nums[i] = i;
        }
        int x = 5;
    
        while (i <= n) {
            int nextMin = Integer.MAX_VALUE;
            for (int z : zs) {
                int y = x / z;
                int j = nextPosGe(nums, y, 1, i);
                while (nums[j] * z <= x) {
                    j = j + 1;
                }
                nextMin = Math.min(nextMin, nums[j] * z);
            }
            x = nextMin;
            nums[i] = x;
            i += 1;
        }
    
        return nums[n];
    }
    
    private int nextPosGe(int[] nums, int y, int start, int end) {
        int i = start, j = end - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (nums[mid] < y) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return i;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.