randomizedselect.java

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

/*
 * 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.
 */
//9 Nov 2007
package cn.edu.whu.iss.algorithm.unit09;

import java.util.ArrayList;
import java.util.List;

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

/**
 * The randomized select by O(n)
 * @author wpc
 * @version 0.0.1
 */
public class RandomizedSelect {

	/**
	 * Get the i-th element by the compare
	 * @param element
	 * @param i
	 * @return
	 */
	public static Object get(Object[] element,int i){
		if(i>element.length){
			return null;
		}
		return getIterate(element,0,element.length-1,i);
	}
	
	/**
	 * Get the middle number of a list and it is a lower number
	 * @param element
	 * @return
	 */
	public static Object getMedian(Object[] element){
		int i = element.length/2;
		return get(element,i);
	}
	
	/**
	 * Get the i-th element by the compare 's number
	 * @param element
	 * @param i
	 * @return i-th
	 */
	public static int getNumber(Object[] element,int i){
		if(i>element.length){
			return element.length-1;
		}
		return getIterateNumber(element,0,element.length-1,i);
	}
	
	/**
	 * Get the i-th element[p..r] by the compare
	 * @param element
	 * @param p
	 * @param r
	 * @param i
	 * @return
	 */
	public static Object get(Object[] element,int p,int r,int i){
		//top flown
		if(i>element.length){
			return null;
		}
		
		if(p==r){
			return element[p];
		}
		
		//Partition the elements by a number
		int q = QuickSort.randomizedPartition(element, p, r);
		int k = q-p+1;
		
		if(i==k){
			return element[q];
		}else if(i<k){
			return get(element,p,q-1,i);
		}else{
			return get(element,q+1,r,i-k);
		}
	}
	
	/**
	 * It search the i-th element by O(n)
	 * And it use the iterate.
	 * @param element
	 * @param p
	 * @param r
	 * @param i
	 * @return
	 */
	public static Object getIterate(Object[] element,int p,int r,int i){
		if(i>element.length){
			return null;
		}
		while(p!=r){
			int q = QuickSort.randomizedPartition(element, p, r);
			int k = q-p+1;
			
			if(i==k){
				return element[q];
			}else if(i<k){
				r=q-1;
			}else{
				p=q+1;
				i=i-k;
			}
		}
		return element[p];
	}
	
	/**
	 * Return the i-th element by the comparable 's number
	 * @param element
	 * @param p
	 * @param r
	 * @param i
	 * @return
	 */
	private static int getIterateNumber(Object[] element,int p,int r,int i){
		if(i>element.length){
			return element.length-1;
		}
		while(p!=r){
			int q = QuickSort.randomizedPartition(element, p, r);
			int k = q-p+1;
			
			if(i==k){
				return q;
			}else if(i<k){
				r=q-1;
			}else{
				p=q+1;
				i=i-k;
			}
		}
		return p;
	}
	
	/**
	 * Find k numbers in the list of element which are the k-th nearest to the middle number
	 * in the element.
	 * @param element
	 * @param k
	 * @return k numbers
	 */
	public static Object[] getKsNearest(Integer[] element,int k){
		Integer x = (Integer.parseInt(getMedian(element).toString()));
		Integer[] D = new Integer[element.length];
		for(int i=0;i<D.length;i++){
			D[i] = Math.abs(x-element[i]);
		}
		Integer t = Integer.parseInt(get(D,k).toString());
		List<Integer> l = new ArrayList<Integer>();
		for(int i=0;i<element.length;i++){
			if(Math.abs(x-element[i])<t){
				l.add(element[i]);
			}
		}
		int i=0;
		while(l.size()<k){
			if(Math.abs(x-element[i])==t){
				l.add(element[i]);
			}
			i++;
		}
		
		return (l.toArray());
		
	}
}