share simple java solution O(nlog(K))based on discussion with my friend! K is range of vlaues


  • 0
    T

    The basic idea is to use binary check. Since the values range is from [-10000,10000], so we can set low=-10000, and high=10000 firstly, then use binary search to check whether we can find a subarray (length>=k) whose average is larger than the target value, where target value is equal to (low+high)/2 every time. After every check, we need to reset low and high value based on checking result. Since the final answer error will be 10^-5, so we can repeat 100 times to make sure our final return value' calculation error will be less than 10^-5 . Here is java solution:

    public class Solution {
        public double findMaxAverage(int[] nums, int k) {
            double low=-100000;
            double high=100000;
            
            int rep=0;
            while(low<high&&rep<100){
                double mid=(low+high)/2;
                if(check(nums,k,mid)){
                    low=mid;
                }else{
                    high=mid;
                }
                
                rep++;
            }
            
            return low;
        }
        
        public boolean check(int[] nums,int k,double target){
            double[] values = new double[nums.length];
            for(int i=0;i<nums.length;i++){
                values[i]=(double)nums[i]-target;
            }
            
            double sum=0;
            double pre_min=0;
            double pre_sum=0;
            
            for(int i=0;i<values.length;i++){
                  sum+=values[i];
                  if(i>=k-1){
                      if(sum-pre_min>=0){
                          return true;
                      }
                      pre_sum+=values[i-(k-1)];
                      pre_min=Math.min(pre_sum,pre_min);
                  }
            }
            
            return false;
        }
    }
    

  • 0
    H

    @tiandiao123 said in share simple java solution O(nlog(K))based on discussion with my friend! K is range of vlaues:

    100000

    nice solution! but i do not know how to calculate the number 100 to make sure less than 10^-5 ,can you explain please?


Log in to reply
 

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