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)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// 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; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment