请教265. paint house II 代码时间复杂度

代码如下，我觉得时间复杂度是n*k^2*log(k)请大神指正，谢谢！

1. class Solution {
   
2.     public int minCostII(int[][] costs) {
   
3.         if (costs == null || costs.length == 0) return 0;
   
4.         if (costs[0] == null || costs[0].length == 0) return 0;
   
5.         int n = costs.length;
   
6.         int k = costs[0].length;
   
7.         int[][] dp = new int[n][k];
   
8.         for (int i = 0; i < k; i++) {
   
9.             dp[0][i] = costs[0][i];
   
10.         }
    
11.         for (int i = 1; i < n; i++) {
    
12.             for (int j = 0; j < k; j++) {
    
13.                 dp[i][j] = costs[i][j] + findMin(i - 1, j, dp);
    
14.             }
    
15.         }
    
16.         int res = Integer.MAX_VALUE;
    
17.         for (int i = 0; i < k; i++) {
    
18.             res = Math.min(res, dp[n - 1][i]);
    
19.         }
    
20.         return res;
    
21.     }
    
22.    
    
23.     public int findMin(int house, int col, int[][] dp) {
    
24.         Queue<Integer> minheap = new PriorityQueue<>();
    
25.         for (int j = 0; j < dp[0].length; j++) {
    
26.             if (j == col) continue;
    
27.             minheap.add(dp[house][j]);
    
28.         }
    
29.         return minheap.poll();
    
30.     }
    
31. }

复制代码

[/i][/i][/i][/i][/i]

你的复杂度分析是没啥问题，但是为什么要用minheap来找最小值呢，直接遍历一遍找最小值不就是O(k)而不是O(klogk)，可以变成O(nk^2)

不知道小帅 发表于 2020-7-2 01:40
你的复杂度分析是没啥问题，但是为什么要用minheap来找最小值呢，直接遍历一遍找最小值不就是O(k)而不是O(k ...

嗯嗯，对的，遍历一遍更快