这里我们会看到一个问题,假设给定一个数组。有n个元素。还给出了另一个值S。我们必须在数组中找到一个元素 K,这样,如果所有大于 K 的元素都等于 K,则最终数组的所有元素之和等于 S。如果不可能,然后返回-1。
假设元素为{12, 6, 3, 7, 8},和值为15,则输出为3。最终数组为{3, 3, 3, 3, 3},数组元素之和为 S = 15
算法
getVal(arr, n, S) −
'Begin
sort arr as increasing order
sum := 0
for i in range 0 to n-1, do
if sum + (arr[i] * (n - i)) is same as S, then
return arr[i]
end if
sum := sum + arr[i]
done
return -1
End
示例
'#include <iostream>
#include <algorithm>
using namespace std;
int getVal(int arr[], int n, int S) {
sort(arr, arr + n);
int sum = 0;
for (int i = 0; i < n; i++) {
if (sum + (arr[i] * (n - i)) == S) //if current value is satisfying, then return arr[i]
return arr[i];
sum += arr[i];
}
return -1;
}
int main() {
int S = 15;
int arr[] = { 12, 3, 6, 7, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << getVal(arr, n, S);
}
输出
'3