对无序数组求中位数的算法

Question

以下算法实现了以o(n)的复杂度对无序数组进行求解中位数的功能，请各位大虾多多指点，以便改进算法！public class MidNum{
public static void main(String args[]){
  int[] a=new int[]{3,5,2,3,5,9};
  int mid=a[0];
  int mid_left=-1;
  int mid_right=-1;
  for(int i=1;i<a.length;i++){
    if(a[i]>mid&&i%2==0){//奇数个且大于
      if(a[i]<mid_right){
         mid_left=mid;
         mid=a[i];
       }else{
        mid_left=mid;
        mid=mid_right;
        mid_right=a[i];   
       }
     
   }else if(a[i]<mid&&i%2!=0){//偶数个且小于
     if(a[i]>mid_left){
         mid_right=mid;
         mid=a[i];
       }else{
        mid_right=mid;   
        mid=mid_left;
        mid_left=a[i];       }   }else if(a[i]<mid&&i%2==0){//奇数个且小于
      //mid=a[i];
      if(mid_left==-1)mid_left=a[i];
      if(a[i]>mid_left)
      mid_left=a[i];
   }else if(a[i]>mid&&i%2!=0){//偶数个且大于
      //mid=a[i];
     if(mid_right==-1)mid_right=a[i];
      if(a[i]<mid_right)
      mid_right=a[i];
   }else if(a[i]==mid){
     mid_right=a[i];
   }System.out.println("mid_left:"+mid_left+"  midNum:"+mid+" mid_right:"+mid_right);
}
System.out.println("midNum:"+mid);
}
}

Answer 1

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
public class MidNumber {
public static void main(String args[]){
int[] a= new int[]{1,1,2,2,8,6,9,5,7,10,4,3,6,49,30,29,6,4,98,56,25,47};
HashSet<Integer> b =new HashSet<Integer> ();
for(int temp:a){
b.add((int)temp);
}
List<Integer> f =new ArrayList<Integer>();
f.addAll(b);
Collections.sort(f);
for(Integer temp:f)
System.out.println(temp);
int size=f.size();
boolean num=(boolean)(size%2==0);

System.out.println(num?(f.get((size-1)/2)+" "+f.get((size+1)/2)):(f.get((size-1)/2)));

}
}

Answer 2

public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0;                //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length));  //求得数组元素的平均数
double k = 0;             //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = avg - (double)array[0];  //用于与K值比较
for(int i = 0; i < array.length; i++){

k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}

}自己想了一个不用排序的,但复杂度也不小

Answer 3

public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0;                //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length));  //求得数组元素的平均数
double k = 0;             //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = Math.abs(avg - (double)array[0]);  //用于与K值比较
for(int i = 0; i < array.length; i++){

k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}

}
有地方写错了,现改为:限制temp的值为正

Answer 4

public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0;                //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length));  //求得数组元素的平均数
double k = 0;             //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = Math.abs(avg - (double)array[0]);  //用于与K值比较
for(int i = 0; i < array.length; i++){

k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}

}
有地方写错了,现改为:限制temp的值为正

Answer 5

public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0;                //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length));  //求得数组元素的平均数
double k = 0;             //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = Math.abs(avg - (double)array[0]);  //用于与K值比较
for(int i = 0; i < array.length; i++){

k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}

}
有地方写错了,现改为:限制temp的值为正

Answer 6

谢谢12楼发表自己的想法，但是算法也是有问题的
int[]array = {1,2,4,3,5,6};
用这个测试，返回4，实际应该返回3，继续探索中

Answer 7

是我没看懂题目，还是怎么回事，求中位数，如为奇数不就是返回下标为(a.length-1)/2的数嘛，如为偶数就返回两个，一个a.length/2-1和a.length/2

Answer 8

无需数列总得先排序吧，那最好的情况（sorted）复杂度也要θ(n)。这几乎不可能发生。
难道可以不排序就得到中间数？

Answer 9

根据中位数的准确概念以及12楼的算法，修改得出以下算法，如发现错误请指出以便改正
public class AAA {
    public static void main(String[]args){
        int[]array = {3,5,2,3,5,9,1,2,11,12,13};
        int n = 0;                //存放数组元素之和
        for(int i = 0; i < array.length; i++){
            n += array[i];
        }
        double avg = (((double)n)/((double)array.length));  //求得数组元素的平均数
        double k = 0;             //用于存放平均数与单个数组元素的差值
        int pivot = array[0];            //用于存放中间值
        int pivot1 = array[0];
        double temp = Math.abs(avg - (double)array[0]);  //用于与K值比较
        for(int i = 1; i < array.length; i++){
            
            k = Math.abs(avg-array[i]);
                       
                if(k < temp||(Math.abs(k-temp)<0.001)){
                pivot1=pivot;
                pivot = array[i];
                temp = k;
            }
   System.out.println(i+" p,p1:"+pivot+","+pivot1+"k:"+k);        }
       if(array.length%2==0){
         System.out.println("p,p1:"+pivot+","+pivot1);
         double tt=((double)pivot+pivot1)/2;
         System.out.println(tt);
        }else{
        System.out.println(pivot);
      }
        
    }
    
}