643. Maximum Average Subarray I (使用 C 語言解題)

643. Maximum Average Subarray I

Solved

Easy

Topics

Companies

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

 

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

 

Constraints:

• n == nums.length
• 1 <= k <= n <= 105
• -104 <= nums[i] <= 104

google 翻譯：

給定一個由 n 個元素組成的整數陣列 nums 和一個整數 k。

找到一個長度等於 k 且平均值最大的連續子數組並傳回該值。 
任何計算誤差小於 10-5 的答案都將被接受。

想法一：

單純的用巢狀迴圈計算出最大值，然後再去平均

寫法一：

double findMaxAverage(int* nums, int numsSize, int k) {
    int for_end = numsSize - (k-1); // 迴圈計算到，因為再往後已經不夠 k 個了
    int max = 0, tmp;
    double ret = 0;
    for(int i=0; i<for_end; i++) {
        tmp = 0;
        for(int j=0; j<k; j++) { // 把 k 個值相加
            tmp += nums[i+j];
        }
        if(tmp > max || !max) // 取最大值 或 第一次也要給值
            max = tmp;
    }
    ret = (double)max / k; // 平均值
    return ret;
}

結果一：

超時了... 果然還是跑太多不必要的迴圈了...

想法二：

先計算k長度的總值，之後再去頭加尾的保持 k 長度。

寫法二：

double findMaxAverage(int* nums, int numsSize, int k) {
    if (numsSize < k) return -1; // 陣列長度不夠 k 就不用計算了

    int left = 0;
    int right = 0;
    int max = 0, sum = 0;
    double ret = 0;

    while(right < k) { // 先算出陣列開頭 k 長度的總值
        sum += nums[right++];
    }
    max = sum; // 目前的最大值

    while(right < numsSize) { // 繼續計算之後的總值
        sum -= nums[left++]; // k 長度的第一個去掉
        sum += nums[right++]; // 把下一個值加入 k 長度裡
        if(sum > max) // 存最大值
            max = sum;
    }
    ret = (double)max / k; // 平均
    return ret;
}

結果二：

結果尚可，但找不到其他可改進的了...