Середнє значення масиву після вилучення деяких елементів рішення штрих-коду


Рівень складності Легко
Часто запитують у Google
масив

Постановка проблеми

У задачі «Середнє значення масиву після видалення деяких елементів» нам надано масив. Усі елементи масиву є натуральними числами. Розмір масиву кратний 20.

Наше завдання - знайти середнє значення масиву виключення найменші 5% елементів і найвищі 5% елементів.

Приклад

arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
4.000000

Пояснення:

Середнє значення масиву після вилучення деяких елементів рішення штрих-коду

Зображення показує даний масив після сортування. Після видалення найвищого та найнижчого 5% елементів сума останнього елемента дорівнює 172, а загальна кількість решти елементів - 36. Отже, середнє стає 4.77778.

Підхід до середнього значення масиву після вилучення деяких елементів

Це проста проблема впровадження. Нижче наведені кроки для вирішення цієї проблеми:

  1. Відсортуйте даний масив, оскільки нам потрібно обрізати з масиву найвищий і найнижчий 5% елементів.
  2. Зберігайте довжину масиву у змінній.
  3. Оголосіть дві змінні:
    1. Для зберігання суми елементів.
    2. Для збереження кількості елементів між ними.
  4. Тепер запустіть цикл і знайдіть суму обрізаних елементів.
    1. Для цього ми ініціалізуємо цикл з n * 0.05, де n - довжина даного масиву, і цикл буде працювати до n * 0.95.
  5. Обчисліть середнє значення.
    1.  Важливим моментом тут є той факт, що він повинен повертати подвійне значення, а не ціле значення.

Реалізація

Код C ++ для середнього значення масиву після видалення деяких елементів

#include <bits/stdc++.h> 
using namespace std; 
    double trimMean(vector<int>& arr) {
        sort(arr.begin(),arr.end());
        int n=arr.size();
        double sum=0,cnt=0;
        for(int i=(n*.05);i<n*.95;i++)
        { 
            sum+=arr[i];
            cnt++;
        }
        return sum/cnt;      
    }
int main() 
{ 
 vector<int> 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}; 
 double ans=trimMean(arr);
 cout<<ans<<endl;
 return 0;
}
4.77778

Код Java для середнього значення масиву після видалення деяких елементів

import java.util.Arrays; 
public class Tutorialcup {
    public static double trimMean(int[] arr) {
     Arrays.sort(arr);
     int n = arr.length;   
     double sum = 0d,cnt=0; 
     for(int i=n / 20;i<n - n / 20;i++)
        { 
            sum+=arr[i];
            cnt++;
        }
        return sum/cnt; 
    }
  public static void main(String[] args) {
        int [] 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}; 
        double ans=trimMean(arr); 
        System.out.println(ans);
  }
}
4.77778

Аналіз складності середнього масиву після вилучення деяких елементів рішення Леткод

Часова складність

Часова складність вищевказаного коду становить O (nlogn) тому що ми сортуємо даний масив. Тут n - довжина даного масиву.

Космічна складність

Складність простору наведеного коду становить O (1) тому що ми використовуємо лише змінну для зберігання відповіді.

посилання