public class WeightedMedian {
@Test
public void main() throws Exception {
    double[] arrays={0.5,1.24,18,1.4,2.1,3.2,2.5,13,2.6,18,2.55,1.2,1.83,1.3,2.1};
    double[] weights={0.8,0.2,1.98,1.4,2.1,3.8,2.1,2.12,0.5,5.6,1.1,1.2,3.5,1.2,1.5};
    System.out.println(getMedian(arrays,weights));
}

/**
 * 求中位数
 * @param arrays 数值数组
 * @param weights 权重数组
 * @return 数值的带权中位数
 * @throws Exception 数值和权重数组长度不一致
 */
private double getMedian(double[] arrays,double[] weights) throws Exception {
    double sum=0;
    double sum1=0;
    //检测数值和权重数组长度是否一致，不一致抛出异常
    if (arrays.length!=weights.length){
        throw new Exception("数值和权重数组长度不一致");
    }else {
        double[] results=new double[arrays.length];
        double[] resultsOfArrays=new double[arrays.length];
        for (int i=0;i<arrays.length;i++) {
            //求出数值和权重的乘积
            results[i] = arrays[i] * weights[i];
        }
        //求出sum
        for (int i=0;i<results.length;i++) {
            //求出带权数值的和
            sum+=results[i];
        }
        //进行数组拷贝，因为执行排序后根据java语言特性数组的顺序会该改变，无法通过下标去查找数值中的中位数
        System.arraycopy(results,0,resultsOfArrays,0,results.length);
        //通过快排进行排序
        quickSort(results,0,results.length-1);
        for (int i=0;i<results.length;i++){
            sum1+=results[i];
            if(sum1>=sum/2){
                //求出中位数索引
                int index=search(resultsOfArrays,results[i]);
                return arrays[index];
            }
        }

    }
    return -1;//返回数值数组的中位数
}

/**
 * 快速排序实现
 * @param arrays 需要排序的数组
 * @param low 数组的低位下标
 * @param high 数组的高位下标
 */
private void quickSort(double[] arrays,int low,int high){
    int i=low;
    int j=high;
    double tmp=arrays[low];
    while (low<high)
    {
        while ((low<high)&&(arrays[high]>=tmp))
        {
            high--;
        }
        arrays[low]=arrays[high];
        arrays[high]=tmp;
        low++;
        while ((low<high)&&(arrays[low]<=tmp))
        {
            low++;
        }
        if (low<high)
        {
            arrays[high]=arrays[low];
            arrays[low]=tmp;
            high--;
        }
    }
    if(i<low-1)
    {
        quickSort(arrays,i,low-1);
    }
    if(low<j)
    {
        quickSort(arrays,low,j);
    }
}

/**
 * 查找实现，此查找只用于此程序，所以在getMedian(double[] arrays,double[] weights)
 * 方法里没有做查找失败检测，因为此查找必然成功。
 * @param arrays 需要查找的数组
 * @param key 需要查找的值
 * @return 返回值所在的数组下标
 */
private int search(double[] arrays,double key)
{
    for (int i=0;i<arrays.length;i++){
        if(arrays[i]==key){
            return i;
        }
    }
    return -1;
}
}
<求教>java算法带权数据求中位数的问题

Ryxzzz

6个回复
