This is the 28th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The title

You are given an array of n integers with indices starting at 0, nums, and an integer k.

The average value of a subarray with radius K is the average value of all elements in a subarray with radius K centered on subindex I in NUMS, that is, the average value of all elements with subindexes in the range i-k and I + K (including i-k and I + K). If there are fewer than k elements before or after subscript I, then the average subarray of radius k is -1.

Construct and return an array AVgs of length N, where AVgs [I] is the average of the subarray with radius K centered on subarray I.

The average of the x elements is the sum of the x elements divided by x. In this case, truncated integer division is used to remove the fractional part of the result.

  • For example, four elements2,3,1 和 5The average value of(2 + 3 + 1 + 5) / 4 = 11/4 = 3.75After truncation, we get3 。

The sample

Input: nums =,4,3,9,1,8,5,2,6 [7], k = 3 output: [1, 1, 1,5,4,4, 1, 1, 1] explanation: -avg [0], AVg [1] and AVg [2] are -1, because the number of elements before each of these subscripts is less than K. - The sum of the elements of the subarray with center subscript 3 and radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37. Using truncated integer division, AVG [3] = 37/7 = 5. - The center is a subarray of subscript 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4. - Center is subarray of subscript 5, AVG [5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4. -AVg [6], AVg [7] and AVg [8] are -1, because the number of elements after these subscripts is less than K.Copy the code
Input: nums = [100000], k = 0 Output: [100000] Explanation: - The sum of elements in a subarray with center subscript 0 and radius 0 is: 100000. Avg [0] = 100,000/1 = 100000.Copy the code
Input: nums = [8], k = 100000 Output: [-1] Explanation: -avg [0] is -1 because the number of elements before and after the subscript 0 is less than K.Copy the code

prompt

  • n == nums.length
  • 1 <= n <= 10^5
  • 0 <= nums[i], k <= 10^5

Their thinking

The sliding window

To calculate the average value of a subarray with a length of K, sliding window is undoubtedly a good way. Fixed the window length k * 2 + 1, calculate the interval sum, and then calculate the average avG and fill it in the corresponding index in the center. Then slide to the right, add elements on the right, subtract elements on the left, and repeat the summation average step above.

class Solution {
    public int[] getAverages(int[] nums, int k) {
        // boundary judgment
        if(k == 0) {return nums;
        }
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        if(n < k * 2 + 1) {return ans;
        }
        
        // Since the range of n is large, we need to use long to count the sum of intervals
        long sum = 0;
        int left = 0, right = 0;
        // Initialize the window interval sum, where the rightmost digit is reserved
        while(right - left < k * 2){
            sum += nums[right++];
        }
        
        while(right < n){
            // Add the rightmost element
            sum += nums[right++];
            // Take the average value and assign it to the middle point
            ans[left + k] = (int)(sum / (k * 2 + 1));
            // Subtract the leftmost element
            sum -= nums[left++];
        }
        
        returnans; }}Copy the code

Complexity analysis

  • Time complexity: O(N)O(N)O(N)
  • Space complexity: O(N)O(N)O(N)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

参 考 答 案 :