Миёнаи массив пас аз нест кардани баъзе унсурҳо Ҳалли Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад 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

Шарҳ:

Миёнаи массив пас аз нест кардани баъзе унсурҳо Ҳалли Leetcode

Дар тасвир массиви додашуда пас аз ҷобаҷогузорӣ нишон дода мешавад. Пас аз хориҷ кардани унсурҳои баландтарин ва пасттарини 5%, ҷамъи элементи боқимонда 172 ва шумораи умумии элементҳои боқимонда 36 мебошанд. Ҳамин тариқ, миёна 4.77778 мешавад.

Равиш барои миёнаи массив пас аз хориҷ кардани баъзе унсурҳои Solution Leetcode

Ин мушкилоти татбиқи осон аст. Дар зер қадамҳои ҳалли ин мушкилот оварда шудаанд:

  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

Таҳлили мураккабии миёнаи массив пас аз бартараф кардани баъзе унсурҳои Solution Leetcode

Мураккабии вақт

Мураккабии вақти рамзи боло дар он аст О (нлогн) зеро мо массиви додашударо ба навъҳо ҷудо карда истодаем. Дар ин ҷо n дарозии массиви додашуда мебошад.

Мураккабии фазо

Мураккабии фазоии рамзи дар боло зикршуда О (1) зеро мо барои тағир додани ҷавоб танҳо як тағирёбандаро истифода мебарем.

Адабиёт