Java 31ms O(nlgk) Solution with Heap


  • 2

    Similar to Ugly Number II, use min-heap to manage numbers.

    public int nthSuperUglyNumber(int n, int[] primes){
        int[] index = new int[1000];
        int[] res = new int[n];
        int[] heap = new int[primes.length];
        for(int i = 0;i<primes.length; i++)heap[i] = primes[i];
        res[0] = 1;
        for(int i = 1; i<n;)
        {
            if(res[i-1] != heap[0]){        	
            	res[i] = heap[0];
            	System.out.print(res[i]+" ");
            	i++;
            }
            updateHeap(heap,primes,index,res);
        }
        return res[n-1];
    }
    public void heapify(int[] heap, int[] primes, int i){
        int index = i;
        int left = 2*i+1; int right = left+1;
        if(heap.length>left && heap[i] > heap[left]) index = left;
        if(heap.length>right && heap[index] > heap[right]) index = right;
        if(i!=index){
            int temp = heap[i];
            heap[i] = heap[index];
            heap[index] = temp;
            int tempPri = primes[i];
            primes[i] = primes[index];
            primes[index] = tempPri;
            heapify(heap,primes,index);
        }
    }
    public void updateHeap(int[] heap, int[] primes, int[] index, int[] res)
    {
        index[primes[0]]++;
        heap[0] = res[index[primes[0]]] * primes[0];
        heapify(heap,primes,0);
    }

  • 0

    You get faster performance for custom heap, if use PriorityQueue, the performance is much more poor


Log in to reply
 

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