Java, O(n*log(k)), dp, heap


  • 0
    M
    public class Solution {
        static class Element implements Comparable<Element> {
            Integer value;
            Integer idx;
            
            public Element(int value, int idx) {
                this.value = value;
                this.idx = idx;
            }
            
            public int compareTo(Element e) {
                return this.value.compareTo(e.value);
            }
        }
        public int nthSuperUglyNumber(int n, int[] primes) {
            int k = primes.length;
            int[] ugly = new int[n];
            int[] indexes = new int[k];
            ugly[0] = 1;
    
            Queue<Element> queue = new PriorityQueue<>();
            for(int i = 0; i < k; i++) 
                queue.offer(new Element(ugly[indexes[i]] * primes[i], i));
            
            for(int i = 1; i < n; i++) {
                int minValue = queue.peek().value;
                ugly[i] = minValue;
                while (queue.peek() != null && queue.peek().value == minValue) { 
                    int idx = queue.poll().idx;
                    indexes[idx]++;
                    queue.offer(new Element(ugly[indexes[idx]] * primes[idx], idx));
                }
            }
    
            return ugly[n - 1];
        }
    }

  • 0

    You have a k-loop inside an n-loop. How is that supposed to be O(n*log(k))?


  • 0
    M

    Oh, you're right Stefan. Solution fixed.
    Thank you!


Log in to reply
 

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