313. Super Ugly Number请教如何优化

我的超时codes如下，基本思路是用minHeap来得到最小值然后加到ArrayList。请教大家如何优化来降低时间复杂度，谢谢

1. public int nthSuperUglyNumber(int n, int[] primes) {
   
2.         if (primes == null || primes.length == 0 || n == 0) return 0;
   
3.         Queue<Integer> minHeap = new PriorityQueue<>();
   
4.         List<Integer> recollect = new ArrayList<>();
   
5.         Set<Integer> check = new HashSet<>();
   
6.         int firstMin = 1;
   
7.         minHeap.add(firstMin);
   
8.         int cnt = n;
   
9.         while (cnt > 0) {
   
10.             for (int prime : primes) {
    
11.                 minHeap.add(prime * firstMin);
    
12.             }
    
13.             cnt--;
    
14.             while (minHeap.peek() <= firstMin) {
    
15.                 int tmp = minHeap.poll();
    
16.                 if (!check.contains(tmp)) {
    
17.                     recollect.add(tmp);
    
18.                     check.add(tmp);
    
19.                 }
    
20.             }
    
21.             firstMin = minHeap.peek();
    
22.         }
    
23.         return recollect.get(n - 1);
    
24.     }

复制代码

minheap前面加一下判断，不让重复元素加进heap。

richarduu 发表于 2020-8-30 06:40
minheap前面加一下判断，不让重复元素加进heap。

请问是不是在第10行下面加： if (minHeap.contains(prime)) continue;
可能我加的不对，还是超时……

小水 发表于 2020-08-29 21:46:00
请问是不是在第10行下面加： if (minHeap.contains(prime)) continue;
可能我加的不对，还是超时……

可以用另外的set去保持唯一性。我建议你看看别人的代码，discussion里面有很多很好的代码可以学的。理解别人的代码比自己一个劲的实现学到的东西多多了

我怀疑不是去重的问题，很大概率是有溢出，所以陷入了死循环。虽然题目保证答案不会溢出，但是中间加入heap的元素是由可能超出int_Max的。你可以试下long，或者尝试打印出最大的数。