selectmedianwithweight.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 69 行

/*
 * Copyright (C) 2000-2007 Wang Pengcheng <[e-mail]>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
//17 Nov 2007
package cn.edu.whu.iss.algorithm.unit09;

import cn.edu.whu.iss.algorithm.unit07.QuickSort;

/**
 * Find the median with weight
 * @author wpc
 * @version 1.0
 * @see WeightAndKeyGet
 */
public class SelectMedianWithWeight {
	/**
	 * Get the location of the median with weight
	 * @param element
	 * @return location
	 */
	public static int getNumber(WeightAndKeyGet[] element){
		return getIterateNumber(element);
	}
	
	/**
	 * Return the median with weight element by the comparable 's number
	 * @param element
	 * @return
	 */
	private static int getIterateNumber(WeightAndKeyGet[] element){
		int p=0;
		int r=element.length-1;
		int k = 0;
		for(int i=0;i<element.length;i++){
			k+=element[i].getWeight();
		}
		k>>=1;//k=k/2
		while(p<r){
			int q = QuickSort.randomizedPartition(element, p, r);
			int tot = 0;
			for(int i=0;i<q+1;i++){
				tot+=element[i].getWeight();
			}
			if(tot==k){
				return q;
			}else if(tot>k){
				r=q-1;
			}else{
				p=q+1;
			}
		}
		return p;
	}
}