정수 배열 arr와 목표 값 대상이 있다고 가정하고 주어진 배열의 값보다 큰 모든 정수를 변경할 때 배열의 합이 다음과 같이 가장 가까운 정수 값을 찾아야 합니다. 타겟 가능. 그것들이 같으면 그러한 정수의 최소값을 반환합니다. 따라서 배열이 [4,9,3]과 같고 대상이 10이면 3을 사용하여 출력은 3이 되고 배열은 [3,3,3]이 되므로 합계는 9, 즉 가장 가까운 요소입니다. 10.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=배열의 크기, avg :=total / n, set sum :=0 및 cnt :=0
- 0 ~ n – 1 범위의 i에 대해
- arr[i] <=avg이면 sum :=sum + arr[i]이고 cnt를 1만큼 증가
- 대상 – 합계 =0이면 평균을 반환합니다.
- 높음 :=(목표 - 합계) / (n - cnt)의 상한
- 낮음 :=(목표 - 합계) / (n - cnt)의 하한
- lowDiff :=|대상 – (낮은*(n - cnt) + 합계)|
- highDiff :=|대상 – (높은*(n - cnt) + 합계)|
- lowDiff <=highDiff이면 low를 반환합니다.
- 높은 수익
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findBestValue(vector<int>& arr, int target) {
int n = arr.size();
int avg = target / n;
int sum = 0;
int cnt = 0;
for(int i = 0; i < n; i++){
if(arr[i] <= avg){
sum += arr[i];
cnt++;
}
}
if(target - sum == 0)return avg;
int high = ceil(((target - sum) * 1.0)/ ((n - cnt) * 1.0));
int low = floor(((target - sum) * 1.0) / ((n - cnt) * 1.0));
int lowDiff = abs(target - (low * (n - cnt) + sum));
int highDiff = abs(target - (high * (n - cnt) + sum));
if( lowDiff <= highDiff)return low;
return high;
}
};
main(){
vector<int> v = {4,9,3,2};
Solution ob;
cout << (ob.findBestValue(v, 10));
} 입력
[4,9,3,2] 10
출력
3