Java C++ 删除元素后数组均值
AnjaVon 人气:0题目要求
思路:模拟
- 根据题意模拟即可:
- 排序然后只取中间符合条件的数加和然后计算均值;
- 根据给出的数组长度n为20的倍数,5%可直接取n/20;
- 两边各去除5%,则剩余长度为0.9n。
Java
class Solution { public double trimMean(int[] arr) { Arrays.sort(arr); int n = arr.length, tot = 0; for (int i = n / 20; i < n - n / 20; i++) tot += arr[i]; return tot / (n * 0.9); } }
- 时间复杂度:O(n log n),为排序复杂度,构造答案复杂度为O(n)
- 空间复杂度:O(log n),为排序复杂度
C++
class Solution { public: double trimMean(vector<int>& arr) { sort(arr.begin(), arr.end()); int n = arr.size(), tot = 0; for (int i = n / 20; i < n - n / 20; i++) tot += arr[i]; return tot / (n * 0.9); } };
- 时间复杂度:O(n log n),为排序复杂度,构造答案复杂度为O(n)
- 空间复杂度:O(log n),为排序复杂度
Rust
impl Solution { pub fn trim_mean(arr: Vec<i32>) -> f64 { let mut res = arr.clone(); let n = arr.len(); res.sort(); res[(n / 20)..(n - n / 20)].iter().sum::<i32>() as f64 / (n as f64 * 0.9) } }
- 时间复杂度:O(n log n),为排序复杂度,构造答案复杂度为O(n)
- 空间复杂度:O(log n),为排序复杂度
加载全部内容