배열의 값으로 평균 원소를 찾는다.

Question

나는 정수 원소의 배열을 가지고있다. 나는 가치에 의한 평균 요소를 찾아야한다. elemets의 양은 이상하고 elemets는 중복 할 수 없다. 예를 들어, 배열 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; 
     } 
     } 
     } 

    }