background

I attended an interview at the beginning of the year , The first round was relatively smooth , I talked in English for nearly an hour about technology , Plus two coding subject . In the second round, I encountered a problem of finding ugly numbers , In fact, this problem is clearly done Leetcode The original title is , But I can't remember the specific idea , The result is very sad .

subject

The title is like this ：

Give you an integer n , Please find out and go back to n individual Ugly number . Ugly number That is, only the prime factor is included 2、3 and / or 5 The positive integer .

I've been thinking a lot lately , There are two ways to solve ：

1. Small cap pile

Ideas

Because it needs to be generated from small to large every time , So the first thought is that we can take advantage of the natural sorting feature of small top heap to take out the smallest ugly number in turn , Then multiply this number by the given prime factor to get the next ugly number , But in the process, the weight needs to be removed , That is, the current ugly number can only be multiplied by the number greater than or equal to the maximum prime factor of the ugly number to get the next ugly number .

Realization

public int nthUglyNumber(int n) {
    
   PriorityQueue<Long> queue = new PriorityQueue<>();
   int[] uglys = {
    5, 3, 2};
   queue.offer(1L);
   long curr = 0;
   while (n-- > 0) {
    
       curr = queue.poll();
       for (int ugly : uglys) {
    
           queue.offer(curr * ugly);
           if (curr % ugly == 0) break;// prune , duplicate removal 
       }
   }
   return (int) curr;
}

Complexity

Time complexity ：O(nlogn)
Spatial complexity ：O(n)

2. Dynamic programming

Ideas

In some scenes with many ugly numbers and prime factors , The method of small top heap will timeout , So we need a better method to achieve ：

Array dp[i]： It means the first one i Ugly number ;
Array uglys[i]： Prime factors that generate ugly numbers ;
The next ugly number = min( Ugly number prime factor * An ugly number that has been generated ), So you need to define an array as a pointer to the generated ugly number ;
Array pointers[i]： Pointer to a generated ugly number in the ugly number generation sequence , Initialize to 0;
Array nums[i]： The next alternative set of ugly numbers , namely ,nums[i] = uglys[i] * dp[pointers[i]]; Each calculation results in nums, And select the smallest element from the set array ; Once the element is selected, it becomes the next ugly number , You need to update pointers[i]（ Self increasing 1, Stands for pointing to the next ugly number ）,nums[i] = uglys[i] * dp[pointers[i]];
The smallest ugly number is 1, take nums[i] Initialize to 1

Realization

public int nthUglyNumber(int n) {
    
    long[] dp = new long[n + 1];
    int[] uglys = {
    5, 3, 2};
    int[] pointers = new int[uglys.length];
    long[] nums = new long[uglys.length];
    Arrays.fill(nums, 1L);
    for (int i = 1; i <= n; i++) {
    
        long min = Arrays.stream(nums).min().getAsLong();
        dp[i] = min;
        for (int j = 0; j < uglys.length; j++) {
    
            if (nums[j] == min) {
    
                pointers[j]++;
                nums[j] = dp[pointers[j]] * uglys[j];
            }
        }
    }
    return (int) dp[n];
}

Complexity

Time complexity ：O(nm)
Spatial complexity ：O(n + m)
m Is the number of ugly prime factors , Change the title to 3

3. Performance comparison

Then verify the comparison between the two methods , It can be seen that the memory consumption is basically the same , The performance improvement of dynamic planning is indeed very obvious ：

replay

The small top of this question is of medium difficulty , Why didn't you even think clearly at that time ？ Although the interview lasted for 3 Appear in hours , I feel my brain can't turn to comfort myself , But the root cause is that I was Leetcode When doing this problem , That is, just do it , Just want to make a quick decision , Didn't spend time thinking and analyzing , There are already debts . Today, we have found the solution of dynamic programming , Indeed, the performance has been improved a lot .