按數組中的值查找平均值元素

Question

我有一個整數元素數組。我需要找到一個平均值的元素。元素的數量是奇數，元素不能重複。 例如，我有一個數組A [5] = {100,43,55,34,68}。所以元素將是55.問題是我需要保存我的數組，我不能使用任何額外的數組，我也無法排序這個數組。

我在想如何找到數組的平均值，然後找到最接近這個值的元素，但對於真正不同的數字，它不會工作。

Answer 1

如果你想在使用恆定數量的內存的時候執行這個任務（我認爲這就是你所說的意思，你沒有提到另外的數組），那麼以線性時間執行這個任務是不可能的。

更確切地說，如果陣列是未觸及的，並且不允許就地排序，那麼在O(nlogn)時間內執行也是不可能的。

您留下了天真的方法：

int NaiveFindMedian(int[] A){ 
    int i, j, count; 

    for (i = 0; i < A.length){ 
     count = 0; 
     for (j = 0; j < A.length; j++) 
      if (A[j] < A[i]) count++; 

     if (count == (A.length-1)/2) return i; 
    } 
} 

顯然，這是昂貴的計算（O(n^2)），但是這是一個使用O(1)內存的價格。如果允許O(n)內存，則可以在O(n)時間內執行此任務。

Answer 2

使用此代碼找到數組元素

import java.util.Scanner; 


    public class AA { 
     public static void main(String[] args) { 


    float b=0,j = 0; 
    float c; 
    int l = 0; 
    Scanner s1=new Scanner(System.in); 
    int x=s1.nextInt(); 
    int[]a =new int[x]; 
    for(int i=0;i<a.length;i++) 
    { 
     a[i]=s1.nextInt(); 
    } 
     for(int i=0;i<a.length;i++) 
     { 
     b=b+a[i]; 
     } 
     float g=a.length; 
     c=b/g; 
     System.out.println("Average="+c); 
     for(int k=0;k<a.length;k++) 
     { 
      for(int h=1+k;h<a.length;h++) 
      { 
       if(b>a[h]) 
       { 
        b=a[h]; 
        int temp=a[h]; 
        a[h]=a[k]; 
        a[k]=temp; 
       } 
      }  
     if(l<a.length-1) 
     { 
       b=a[++l]; 

     } 
     } 
     for(int i=0;i<a.length;i++) 
     { 
     if(c<a[i]) 
     { 
      float v=a[i]-c; 
      float s=a[i-1]-c; 
      if(s<0) 
      { 
        j=s*(-1); 
      } 
      if(v==j) 
        { 
         System.out.println("Array Element NearBy="+a[i-1]+" or "+a[i]); 
        } 
      else if(v>j) 
      { 
       System.out.println("Array Element NearBy="+a[i-1]); 
      } 
      else 
      { 
       System.out.println("Array Element NearBy="+a[i]); 
      } 
      break; 
     } 
     } 
     } 

    }