计算平均值，然后将最接近的元素返回到平均值

我想计算双精度数组的平均值，然后将数组中最接近的元素的值返回到计算的平均值。但是我使用的算法是O（2n）。是否可以确定最接近平均值的元素，同时仍然计算平均值？我想不是。计算平均值，然后将最接近的元素返回到平均值

#include <iostream> 
#include <cmath> 
using namespace std; 

double* aver(double* arr, size_t size, double& average){ 
    for(int i = 0; i < size; i++) 
     average+=arr[i]; 
    average/=size; 
    double* ret = arr; 
    for(int i = 0; i < size; i++){ 
     if(abs(arr[i] - average) < abs(*ret - average)){ 
      *ret = arr[i]; 
     } 
    } 
    return ret; 
} 

int main(){ 
    double arr[] = {1,2,3,4,5,7}; 
    size_t size = sizeof(arr)/sizeof(arr[0]); 
    double average = 0; 
    double* p = aver(arr, size, average); 
    cout<< *p << " " << average << endl; 
    return 0; 
}

来源

2014-03-25 Yoda

数组是否会按排序顺序？如果是的话我们可以优化我们的循环 – 999k

可能有一个聪明的窍门，即在一次传递中同时获得平均值和最接近平均值的元素，但它可能不会产生任何类型的实际性能差异，因为O（n）和O（2n）是相同的东西。 –

你检查了这个问题的其他答案http://stackoverflow.com/q/19504289/1151831 – 999k

-1

如果对数组进行排序，则可以通过简单的O（logn）二分搜索找到最接近目标的元素。如果它没有排序，那么这是一个线性搜索。作为一个侧面说明，O（2n）可能会有直观的意义，但从数学上讲，它与O（n）没有什么不同。

来源

2014-03-25 17:12:09 Blindy

在数组中完全非负值的前提下，你可以使用这个适应你的代码：

#include <iostream> 
#include <cmath> 
using namespace std; 

double* aver(double* arr, size_t size, double& average){ 
    int iclosest = 0; 
    for(int i = 0; i < size; i++) { 
     average+=arr[i]; 
     if (abs(arr[iclosest + 1] - average/(i+1)) < abs(arr[iclosest] - average/(i+1))) 
      ++iclosest; 
    } 
    average/=size; 
    return &arr[iclosest]; 
} 

int main(){ 
    //double arr[] = {1,2,3,4,5,7}; 
    double arr[] = {4,5,3,2,1,7}; 
    size_t size = sizeof(arr)/sizeof(arr[0]); 
    double average = 0; 
    double* p = aver(arr, size, average); 
    cout<< *p << " " << average << endl; 
    return 0; 
}

它可以适应负值工作，无论是。

但是，我说同意Blindy直至O（2n）= O（n）有关。

来源

2014-03-25 17:53:58

计算平均值，然后将最接近的元素返回到平均值

回答

相关问题