Friday, December 25, 2015

[LeetCode] SuperUglyNumber

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primeCollection) {
        if (primeCollection == null || primeCollection.length == 0) return 0;
        
        ArrayList<Integer> superUglyNumberCollection = new ArrayList<Integer>();
        superUglyNumberCollection.add(1);
        int[] lastNumberIndex = new int[primeCollection.length];
        
        for (int i = 2; i <= n; i++) {
            int possibleNumber = primeCollection[0] * superUglyNumberCollection.get(lastNumberIndex[0]);
            for (int j = 1; j < primeCollection.length; j++) {
                possibleNumber = Math.min(possibleNumber, primeCollection[j] * superUglyNumberCollection.get(lastNumberIndex[j]));
            }
            superUglyNumberCollection.add(possibleNumber);
            for (int j = 0; j < primeCollection.length; j++) {
                if (possibleNumber == primeCollection[j] * superUglyNumberCollection.get(lastNumberIndex[j])) {
                    lastNumberIndex[j]++;
                }
            }
        }
        
        return superUglyNumberCollection.get(n-1);
    }
}
Wrong one:
public class Solution {
    public int nthSuperUglyNumber(int n, int[] primeCollection) {
        if (primeCollection == null || primeCollection.length == 0) return 0;
        
        ArrayList<Integer> superUglyNumberCollection = new ArrayList<Integer>();
        superUglyNumberCollection.add(1);
        int[] lastNumberIndex = new int[primeCollection.length];
        
        for (int i = 2; i <= n; i++) {
            int possibleNumber = primeCollection[0] * superUglyNumberCollection.get(lastNumberIndex[0]);
            for (int j = 1; j < primeCollection.length; j++) {
                possibleNumber = Math.min(possibleNumber, primeCollection[j] * superUglyNumberCollection.get(lastNumberIndex[j]));
            }
            superUglyNumberCollection.add(possibleNumber);
            for (int j = 0; j < primeCollection.length; j++) {
                if (possibleNumber == primeCollection[j] * superUglyNumberCollection.get(lastNumberIndex[j])) {
                    lastNumberIndex[j]++;
                    break; //This doesn't account for duplicates
                }
            }
        }
        
        return superUglyNumberCollection.get(n-1);
    }
}

No comments:

Post a Comment