用排序，快速选择 2 种算法，用 slice / array_slice / Arrays.copyOfRange / ToList().GetRange / memcpy / 新建 vector 指定指针分割列表，传递回调函数，求解《1619. 删除某些元素后的数组均值》
例题
1619. 删除某些元素后的数组均值
给你一个整数数组 arr ，请你删除最小 5% 的数字和最大 5% 的数字后，剩余数字的平均值。
与 标准答案 误差在 10-5 的结果都被视为正确结果。
示例 1：
输入：arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]
输出：2.00000
解释：删除数组中最大和最小的元素后，所有元素都等于 2，所以平均值为 2 。
示例 2：
输入：arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
输出：4.00000
示例 3：
输入：arr = [6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
输出：4.77778
示例 4：
输入：arr = [9,7,8,7,7,8,4,4,6,8,8,7,6,8,8,9,2,6,0,0,1,10,8,6,3,3,5,1,10,9,0,7,10,0,10,4,1,10,6,9,3,6,0,0,2,7,0,6,7,2,9,7,7,3,0,1,6,1,10,3]
输出：5.27778
示例 5：
输入：arr = [4,8,4,10,0,7,1,3,7,8,8,3,4,1,6,2,1,1,8,0,9,8,0,3,9,10,3,10,1,10,7,3,2,1,4,9,10,7,6,4,0,8,5,1,2,1,6,2,5,0,7,10,9,10,3,7,10,5,8,5,7,6,7,6,10,9,5,10,5,5,7,2,10,7,7,8,2,0,1,1]
输出：5.29167
提示：
20 <= arr.length <= 1000
arr.length 是 20 的 倍数
0 <= arr[i] <= 105
答案
排序
var trimMean = function(arr) {
const n = arr.length, delNum = n / 20 | 0
return arr.sort((a, b) => a - b).slice(delNum, n - delNum).reduce((p, v) => p + v) / (n * 0.9)
};function trimMean(arr: number[]): number {
const n = arr.length
arr.sort((a, b) => a - b)
let sum = 0
for (let i = n / 20 | 0; i < (n / 20 * 19 | 0); i++) sum += arr[i]
return sum / (n * 0.9)
};class Solution {
function trimMean($arr) {
$n = count($arr);
$delNum = $n / 20 | 0;
sort($arr, SORT_NUMERIC);
return array_sum(array_slice($arr, $delNum, $n - ($delNum << 1))) / ($n * 0.9);
}
}func trimMean(arr []int) float64 {
n := len(arr)
sort.Ints(arr)
delNum, sum := n / 20 | 0, 0
for _, v := range arr[delNum : n - delNum] {
sum += v
}
return float64(sum) / (float64(n) * 0.9)
}class Solution {
public double trimMean(int[] arr) {
int n = arr.length, delNum = n / 20 | 0;
Arrays.sort(arr);
return Arrays.stream(Arrays.copyOfRange(arr, delNum, n - delNum)).sum() / (n * .9);
}
}public class Solution {
public double TrimMean(int[] arr) {
int n = arr.Length, delNum = n / 20 | 0;
Array.Sort(arr);
return arr.ToList().GetRange(delNum, n - (delNum << 1)).Sum() / (n * .9);
}
}static inline int cmp (const void* pa, const void* pb) {
return *(int*)pa - *(int*)pb;
}
double trimMean(int* arr, int arrSize){
int delNum = arrSize / 20 | 0;
qsort(arr, arrSize, sizeof(int), cmp);
int desLen = (int)arrSize * .9;
int* des = malloc(sizeof(int) * desLen);
memcpy(des, arr + delNum, desLen * sizeof(int));
double desSum = 0;
for (int i = 0; i < desLen; i++) desSum += des[i];
return desSum / desLen;
}class Solution {
public:
double trimMean(vector<int>& arr) {
int n = arr.size(), delNum = n / 20 | 0;
sort(arr.begin(), arr.end());
vector<int> des = vector<int>(arr.begin() + delNum, arr.end() - delNum);
return accumulate(des.begin(), des.end(), 0) / (n * .9);
}
};class Solution:
def trimMean(self, arr: List[int]) -> float:
n = len(arr)
delNum = n // 20
return sum(sorted(arr)[delNum:n - delNum]) / (n * .9)class Solution:
def trimMean(self, arr: List[int]) -> float:
n = len(arr)
arr.sort()
return sum(arr[n // 20 : n // 20 * 19]) / (n * .9)快速选择
var trimMean = function(arr) {
const n = arr.length, delNum = n / 20 | 0
quickSelect(arr, 0, n - 1, delNum, (a, b) => a - b)
arr = arr.slice(delNum)
quickSelect(arr, 0, n - 1 - delNum, delNum, (a, b) => b - a)
return arr.slice(delNum).reduce((p, v) => p + v) / (n * .9)
};
const quickSelect = (nums, start, end, k, cb) => {
swap(nums, start , (start + end + (start + end >> 1)) / 3 | 0)
const pivot = nums[start]
let l = start, i = start + 1, r = end
while (i <= r) {
const d = cb(nums[i], pivot)
if (d > 0) swap(nums, i, r--)
else if (d < 0) swap(nums, i++, l++)
else i++
}
if (l === k) return
return l < k ? quickSelect(nums, l + 1, end, k, cb) : quickSelect(nums, start, l - 1, k, cb)
}
const swap = (nums, a, b) => {
nums[b] = nums[a] + nums[b] - (nums[a] = nums[b])
}function trimMean(arr: number[]): number {
const n = arr.length, k = n / 20 | 0
quickSelect(arr, 0, n - 1, k, (a, b) => a - b)
arr = arr.slice(k)
quickSelect(arr, 0, n - 1 - k, k, (a, b) => b - a)
return arr.slice(k).reduce((p, v) => p + v) / (n * .9)
};
const quickSelect = (nums: number[], start: number, end: number, k: number, cb: (a:number, b:number) => number) => {
swap(nums, start, (start + end + (start + end >> 1)) / 3 | 0)
const pivot = nums[start]
let l = start, i = l + 1, r = end
while (i <= r) {
const d = cb(nums[i], pivot)
if (d > 0) swap(nums, i, r--)
else if (d < 0) swap(nums, i++, l++)
else i++
}
if (l === k) return
return l < k ? quickSelect(nums, l + 1, end, k, cb) : quickSelect(nums, start, l - 1, k, cb)
}
const swap = (nums, a, b) => {
const t = nums[a]
nums[a] = nums[b]
nums[b] = t
}class Solution {
function trimMean($arr) {
$n = count($arr);
$k = $n / 20 | 0;
$this->quickSelect($arr, 0, $n - 1, $k, fn($a, $b) => $a - $b);
$arr = array_slice($arr, $k);
$this->quickSelect($arr, 0, $n - 1 - $k, $k, fn($a, $b) => $b - $a);
return array_sum(array_slice($arr, $k)) / ($n * .9);
}
function quickSelect(&$nums, $start, $end, $k, $cb) {
$this->swap($nums, $start, ($start + $end + ($start + $end >> 1)) / 3 | 0);
$pivot = $nums[$start];
$l = $start;
$i = $l + 1;
$r = $end;
while ($i <= $r) {
$d = $cb($nums[$i], $pivot);
if ($d > 0) $this->swap($nums, $i, $r--);
elseif ($d < 0) $this->swap($nums, $i++, $l++);
else $i++;
}
if ($l === $k) return;
return $l < $k ? $this->quickSelect($nums, $l + 1, $end, $k, $cb)
: $this->quickSelect($nums, $start, $l - 1, $k , $cb);
}
function swap(&$nums, $a, $b) {
[$nums[$a], $nums[$b]] = [$nums[$b], $nums[$a]];
}
}func trimMean(arr []int) float64 {
n := len(arr)
k := n / 20
quickSelect(arr, 0, n - 1, k, func(a, b int) int {
return a - b
})
arr = arr[k:]
quickSelect(arr, 0, n - 1 - k, k, func(a, b int) int {
return b - a
})
sum := 0
for i := k; i < n - k; i++ {
sum += arr[i]
}
return float64(sum) / (float64(n) * .9)
}
func quickSelect(nums []int, start int, end int, k int, cb func(int, int) int) {
swap(nums, start, (start + end + (start + end) >> 1) / 3)
pivot, l, i, r := nums[start], start, start + 1, end
for i <= r {
d := cb(nums[i], pivot)
if d > 0 {
swap(nums, i, r)
r--
} else if d < 0 {
swap(nums, i, l)
i, l = i + 1, l + 1
} else {
i++
}
}
if l == k {
return
}
if l < k {
quickSelect(nums, l + 1, end, k, cb)
} else {
quickSelect(nums, start, l - 1, k, cb)
}
}
func swap(nums []int, a int, b int) {
nums[a], nums[b] = nums[b], nums[a]
}interface Callable {
public Integer call(Integer a, Integer b);
}
class Solution {
public double trimMean(int[] arr) {
int n = arr.length, k = n / 20;
quickSelect(arr, 0, n - 1, k, (a, b) -> a - b);
arr = Arrays.copyOfRange(arr, k, n);
quickSelect(arr, 0, n - 1 - k, k, (a, b) -> b - a);
return Arrays.stream(Arrays.copyOfRange(arr, k, n)).sum() / (n * .9);
}
public void quickSelect(int[] nums, int start, int end, int k, Callable cb) {
swap(nums, start, (start + end + (start + end >> 1)) / 3);
int pivot = nums[start], l = start, i = l + 1, r = end;
while (i <= r) {
int d = cb.call(nums[i], pivot);
if (d > 0) swap(nums, i, r--);
else if (d < 0) swap(nums, i++, l++);
else i++;
}
if (l == k) return;
if (l < k) quickSelect(nums, l + 1, end, k, cb);
else quickSelect(nums, start, l - 1, k, cb);
}
public void swap(int[] nums, int a, int b) {
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
}public class Solution {
public double TrimMean(int[] arr) {
int n = arr.Length, k = n / 20;
quickSelect(arr, 0, n - 1, k, (a, b) => a - b);
arr = arr.ToList().GetRange(k, n - k).ToArray();
quickSelect(arr, 0, n - 1 - k, k, (a, b) => b - a);
return arr.ToList().GetRange(k, n - (k << 1)).Sum() / (n * .9);
}
public void quickSelect(int[] nums, int start, int end, int k, Func<int, int, int> cb) {
swap(nums, start, (start + end + (start + end >> 1)) / 3);
int pivot = nums[start];
int l = start, i = l + 1, r = end;
while (i <= r) {
int d = cb(nums[i], pivot);
if (d > 0) swap(nums, i, r--);
else if (d < 0) swap(nums, i++, l++);
else i++;
}
if (l == k) return;
if (l < k) quickSelect(nums, l + 1, end, k, cb);
else quickSelect(nums, start, l - 1, k, cb);
}
public void swap(int[] nums, int a, int b) {
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
}void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int asc(int a, int b) {
return a - b;
}
int desc(int a, int b) {
return b - a;
}
void quickSelect(int* nums, int start, int end, int k, int (*cb)(int, int)) {
swap(&nums[start], &nums[(start + end + (start + end >> 1)) / 3 | 0]);
int pivot = nums[start], l = start, i = l + 1, r = end;
while (i <= r) {
int d = cb(nums[i], pivot);
if (d > 0) swap(&nums[i], &nums[r--]);
else if (d < 0) swap(&nums[i++], &nums[l++]);
else i++;
}
if (l == k) return;
if (l < k) quickSelect(nums, l + 1, end, k, cb);
else quickSelect(nums, start, l - 1, k, cb);
}
double trimMean(int* arr, int arrSize){
int k = arrSize / 20;
quickSelect(arr, 0, arrSize - 1, k, asc);
int* dest = malloc(sizeof(int) * (arrSize - k));
memcpy(dest, arr + k, (arrSize - k) * sizeof(int));
quickSelect(dest, 0, arrSize - 1 - k, k, &desc);
int sum = 0;
for (int i = k; i < arrSize - k; i++) sum += dest[i];
return sum / (arrSize * .9);
}class Solution {
public:
double trimMean(vector<int>& arr) { // 自行实现
int n = arr.size(), k = n / 20;
quickSelect(arr, 0, n - 1, k, [](int a, int b)->int {
return a - b;
});
arr = vector<int>(arr.begin() + k, arr.end());
quickSelect(arr, 0, n - 1 - k, k, [](int a, int b)->int {
return b - a;
});
return accumulate(arr.begin() + k, arr.end(), 0) / (n * .9);
}
void quickSelect(vector<int>& nums, int start, int end, int k, function<int(int, int)> cb) {
swap(nums[start], nums[(start + end + (start + end >> 1)) / 3]);
int pivot = nums[start], l = start, i = l + 1, r = end;
while (i <= r) {
int d = cb(nums[i], pivot);
if (d > 0) swap(nums[i], nums[r--]);
else if (d < 0) swap(nums[i++], nums[l++]);
else i++;
}
if (l == k) return;
if (l < k) quickSelect(nums, l + 1, end, k, cb);
else quickSelect(nums, start, l - 1, k, cb);
}
};class Solution {
public:
double trimMean(vector<int>& arr) { // 使用系统函数 nth_element
int n = arr.size(), k = n / 20;
nth_element(arr.begin(), arr.begin() + k, arr.end());
nth_element(arr.rbegin(), arr.rbegin() + k, arr.rend(), greater<int>());
return accumulate(arr.begin() + k, arr.end() - k, 0) / (n * .9);
}
};class Solution:
def trimMean(self, arr: List[int]) -> float:
n = len(arr)
k = n // 20
self.quickSelect(arr, 0, n - 1, k, lambda a, b: a - b)
arr = arr[k:]
self.quickSelect(arr, 0, n - 1 - k, k, lambda a, b: b - a)
return sum(arr[k:]) / (n * .9)
def quickSelect(self, nums: List[int], start: int, end: int, k: int, cb: Callable[[int, int], int]):
self.swap(nums, start, (start + end + (start + end >> 1)) // 3)
pivot, l, i, r = nums[start], start, start + 1, end
while i <= r:
d = cb(nums[i], pivot)
if d > 0:
self.swap(nums, i, r)
r -= 1
elif d < 0:
self.swap(nums, i, l)
i, l = i + 1, l + 1
else: i += 1
if l == k: return
if l < k: self.quickSelect(nums, l + 1, end, k, cb)
else: self.quickSelect(nums, start, l - 1, k, cb)
def swap(self, nums: List[int], a: int, b: int):
nums[a], nums[b] = nums[b], nums[a]