花花酱 LeetCode 1491. Average Salary Excluding the Minimum and Maximum Salary

By zxi on June 27, 2020

Given an array of unique integers salary where salary[i] is the salary of the employee i.

Return the average salary of employees excluding the minimum and maximum salary.

Example 1:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000)/2= 2500

Example 2:

Input: salary = [1000,2000,3000]
Output: 2000.00000
Explanation: Minimum salary and maximum salary are 1000 and 3000 respectively.
Average salary excluding minimum and maximum salary is (2000)/1= 2000

Example 3:

Input: salary = [6000,5000,4000,3000,2000,1000]
Output: 3500.00000

Example 4:

Input: salary = [8000,9000,2000,3000,6000,1000]
Output: 4750.00000

Constraints:

3 <= salary.length <= 100
10^3 <= salary[i] <= 10^6
salary[i] is unique.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: Brute Force

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

double average(vector<int>& salary) {

auto [lit, hit] = minmax_element(begin(salary), end(salary));

int sum = accumulate(begin(salary), end(salary), 0);

return (sum - *lit - *hit) * 1.0 / (salary.size() - 2);

}

};

花花酱 LeetCode 643. Maximum Average Subarray I

By zxi on July 16, 2018

Problem

题目大意：找出k长度的子数组的平均值的最大值。

https://leetcode.com/problems/maximum-average-subarray-i/description/

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

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

Note:

1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].

Solution: Sliding Window

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 124 ms

class Solution {

public:

double findMaxAverage(vector<int>& nums, int k) {

const int n = nums.size();

int sum = 0;

int ans = INT_MIN;

for (int i = 0; i < n; ++i) {

if (i >= k) sum -= nums[i - k];

sum += nums[i];

if (i + 1 >= k) ans = max(ans, sum);

}

return static_cast<double>(ans) / k;

}

};

Problem

题目大意：把一个数组分成k个段，求每段平均值和的最大值。

https://leetcode.com/problems/largest-sum-of-averages/description/

We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?

Note that our partition must use every number in A, and that scores are not necessarily integers.

Example:
Input: 
A = [9,1,2,3,9]
K = 3
Output: 20
Explanation: 
The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

Note:

1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
Answers within 10^-6 of the correct answer will be accepted as correct.

Idea

DP, use dp[k][i] to denote the largest average sum of partitioning first i elements into k groups.

Init

dp[1][i] = sum(a[0] ~ a[i – 1]) / i, for i in 1, 2, … , n.

Transition

dp[k][i] = max(dp[k – 1][j] + sum(a[j] ~ a[i – 1]) / (i – j)) for j in k – 1,…,i-1.

that is find the best j such that maximize dp[k][i]

largest sum of partitioning first j elements (a[0] ~ a[j – 1]) into k – 1 groups (already computed)

+ average of a[j] ~ a[i – 1] (partition a[j] ~ a[i – 1] into 1 group).

Answer

dp[K][n]

Solution 1: DP

Time complexity: O(kn^2)

Space complexity: O(kn)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

double largestSumOfAverages(vector<int>& A, int K) {

const int n = A.size();

vector<vector<double>> dp(K + 1, vector<double>(n + 1, 0.0));

vector<double> sums(n + 1, 0.0);

for (int i = 1; i <= n; ++i) {

sums[i] = sums[i - 1] + A[i - 1];

dp[1][i] = static_cast<double>(sums[i]) / i;

}

for (int k = 2; k <= K; ++k)

for (int i = k; i <= n; ++i)

for (int j = k - 1; j < i; ++j)

dp[k][i] = max(dp[k][i], dp[k - 1][j] + (sums[i] - sums[j]) / (i - j));

return dp[K][n];

}

};

C++ O(n) space

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

double largestSumOfAverages(vector<int>& A, int K) {

const int n = A.size();

vector<double> dp(n + 1, 0.0);

vector<double> sums(n + 1, 0.0);

for (int i = 1; i <= n; ++i) {

sums[i] = sums[i - 1] + A[i - 1];

dp[i] = static_cast<double>(sums[i]) / i;

}

for (int k = 2; k <= K; ++k) {

vector<double> tmp(n + 1, 0.0);

for (int i = k; i <= n; ++i)

for (int j = k - 1; j < i; ++j)

tmp[i] = max(tmp[i], dp[j] + (sums[i] - sums[j]) / (i - j));

dp.swap(tmp);

}

return dp[n];

}

};

Solution 2: DFS + memoriation

C++

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

double largestSumOfAverages(vector<int>& A, int K) {

const int n = A.size();

m_ = vector<vector<double>>(K + 1, vector<double>(n + 1, 0.0));

sums_ = vector<double>(n + 1, 0.0);

for (int i = 1; i <= n; ++i)

sums_[i] = sums_[i - 1] + A[i - 1];

return LSA(A, n, K);

}

private:

vector<vector<double>> m_;

vector<double> sums_;

// Largest sum of averages for first n elements in A paritioned into k groups

double LSA(const vector<int>& A, int n, int k) {

if (m_[k][n] > 0) return m_[k][n];

if (k == 1) return sums_[n] / n;

for (int i = k - 1; i < n; ++i)

m_[k][n] = max(m_[k][n], LSA(A, i, k - 1) + (sums_[n] - sums_[i]) / (n - i));

return m_[k][n];

}

};

花花酱 LeetCode 805. Split Array With Same Average

By zxi on March 24, 2018

Problem

题目大意：问能否将一个数组分成两部分，每部分的平均值相同。

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.

Note:

The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000].

Solution: Search

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: 771 ms

class Solution {

public:

bool splitArraySameAverage(vector<int>& A) {

std::sort(A.begin(), A.end());

sum = std::accumulate(A.begin(), A.end(), 0);

n = A.size();

return dfs(A, 1, 0, 0);

}

private:

int sum;

int n;

bool dfs(const vector<int>& A, int c, int s, int cur) {

if (c > A.size() / 2) return false;

for (int i = s; i < A.size(); ++i) {

cur += A[i];

if (cur * (n - c) == (sum - cur) * c) return true;

if (cur * (n - c) > (sum - cur) * c) break;

if (dfs(A, c + 1, i + 1, cur)) return true;

cur -= A[i];

}

return false;

}

};

Posts tagged as “average”

花花酱 LeetCode 1491. Average Salary Excluding the Minimum and Maximum Salary

Solution: Brute Force

C++

花花酱 LeetCode 643. Maximum Average Subarray I

Problem

Solution: Sliding Window

Related Problems

花花酱 LeetCode 813. Largest Sum of Averages

Problem

Idea

Init

Transition

Answer

Solution 1: DP

C++

C++ O(n) space

Solution 2: DFS + memoriation

C++

花花酱 LeetCode 805. Split Array With Same Average

Problem

Solution: Search