LeetCode每日一题(1300. Sum of Mutated Array Closest to Target)

Given an integer array arr and a target value target, return the integer value such that when we change all the integers larger than value in the given array to be equal to value, the sum of the array gets as close as possible (in absolute difference) to target.

In case of a tie, return the minimum such integer.

Notice that the answer is not neccesarilly a number from arr.

Example 1:

Input: arr = [4,9,3], target = 10
Output: 3

Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that’s the optimal answer.

Example 2:

Input: arr = [2,3,5], target = 10
Output: 5

Example 3:

Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361

Constraints:

• 1 <= arr.length <= 104
• 1 <= arr[i], target <= 105

---

太难表达了， 不写了， 看代码吧

---

impl Solution {
    pub fn find_best_value(mut arr: Vec<i32>, target: i32) -> i32 {
        arr.sort();
        let ori = arr.clone();
        let mut total = arr.len() as i32;
        let arr = arr.into_iter().fold(Vec::new(), |mut l, v| {
            if let Some((last_val, mut last_count)) = l.pop() {
                if last_val == v {
                    last_count += 1;
                    l.push((last_val, last_count));
                    return l;
                }
                l.push((last_val, last_count));
            }
            l.push((v, 1));
            return l;
        });
        let mut sum = 0;
        let mut diffs = Vec::new();
        let mut prev = i32::MIN;
        for (v, c) in arr {
            if target < sum {
                break;
            }
            let d = (target - sum) / total;
            if d <= v && d > prev {
                diffs.push((((sum + d * total) - target).abs(), d));
            }
            if d + 1 <= v && d + 1 > prev {
                diffs.push((((sum + (d + 1) * total) - target).abs(), d + 1));
            }
            sum += v * c;
            total -= c;
            prev = v;
        }
        if diffs.is_empty() {
            return *ori.last().unwrap();
        }
        diffs.sort();
        diffs[0].1
    }
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42