java o(n), very simples long as get the idea


  • 0
    L
    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
            if(nuts==null||tree==null||squirrel==null||nuts.length==0) return 0;
            int len=nuts.length;
            int [][]dist=new int[len][2];
            int minDist=Integer.MAX_VALUE;
            int sum=0;
            for(int i=0;i<len;i++){
                int a=calDist(nuts[i],tree);
                int b=calDist(nuts[i],squirrel);
                dist[i][0]=a;
                dist[i][1]=b;
                sum+=2*a;
                minDist=Math.min(minDist,b-a);
            }
            return sum+minDist;
        }
        
        private int calDist(int []a,int []b){
            return Math.abs(a[0]-b[0])+Math.abs(a[1]-b[1]);
        }
    

  • 0

    If n is the number of nuts, then this isn't o(n). Only O(n).


Log in to reply
 

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