My Accept Java O(NK) solution


  • 0
    W

    The basic idea is using two temporary lists to store the index of the minimum number in a row and the second minimum number in a row.

    public int minCostII(int[][] costs) {
            int len=costs.length;
            if(len==0) return 0;
            int k=costs[0].length;
            if(k==0) return 0;
            int[] costMap=new int[k];
            for(int i=0;i<len;i++){
                int[] tmp=new int[k];
                List<Integer> listMin1=new ArrayList<Integer>();
                List<Integer> listMin2=new ArrayList<Integer>();
                for(int j=0;j<k;j++){
                    tmp[j]=costMap[j];
                    if(listMin1.size()==0) listMin1.add(j);
                    else if(tmp[j]<tmp[listMin1.get(0)]){
                        listMin2=listMin1;
                        listMin1=new ArrayList<Integer>();
                        listMin1.add(j);
                    }else if(tmp[j]==tmp[listMin1.get(0)]) listMin1.add(j);
                    else if(listMin2.size()==0) listMin2.add(j);
                    else if(tmp[j]<tmp[listMin2.get(0)]){
                        listMin2=new ArrayList<Integer>();
                        listMin2.add(j);
                    }else if(tmp[j]==tmp[listMin2.get(0)]) listMin2.add(j);
                }
                for(int j=0;j<k;j++)
                    if(i==0) costMap[j]=costs[0][j];
                    else if(listMin1.size()==1 && j==listMin1.get(0)) costMap[j]=tmp[listMin2.get(0)]+costs[i][j];
                    else costMap[j]=tmp[listMin1.get(0)]+costs[i][j];
            }
            int min=costMap[0];
            for(int costSum : costMap)
                min=Math.min(min, costSum);
            return min;
        }

Log in to reply
 

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