23ms JAVA ,easy to kill duplicates


  • -1
    D
    public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int len = primes.length;
        int [] res = new int [n];
        int [] idx = new int [len];
        res[0] = 1;
        for(int i =1;i<n;i++){
            int min = Integer.MAX_VALUE;
            for(int j=0;j<len;j++){
                int temp2 = primes[j]*res[idx[j]];
                if(temp2 == res[i-1]){
                    idx[j]++;        // kill duplicate
                    temp2 = primes[j]*res[idx[j]];
                }
                if(temp2 < min)
                    min =temp2;
                
            }
            res[i]  = min;
        }
        return res[n-1];
    }
    

    }


  • 0
    A

    if(temp2 == res[i-1]){

    why does it only compare the previous res to detect duplication?


  • 0
    D

    In usual, when we determine a new smallest ugly number, people then use loop to kill duplicates equals this new smallest ugly number.
    But if we keep duplicates exist this loop and kill them in next i loop, res[i-1] is the duplicates what we want to kill in previous loop


Log in to reply
 

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