`
leonzhx
  • 浏览: 793433 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Question 3c Finding Smallest K Numbers

阅读更多

A even more effective way dealing with this problem is to use linear time selection. The major idea of linear time selection is to recursively invoke the partition subroutine like a qucik sort which use a pivot to partition the array. After it finds the kth smallest element, all the elements less than or equals to it are relocated to the left of the pivot and those bigger than it are relocated to the right. So the solution to the original problem is to output all left elements to the kth smallest element and including itself.

 

The process of utilizing the partition subroutine to find the kth smallest element is like below :

    1) Choose a pivot to partition the whole array, after partion all elements less than or equals to the pivot are relocated to the left of the pivot and those bigger than the pivot are relocated to the right.

    2) Suppose the position of the pivot after partition is p, if p == k , then you find the kth smallest element otherwise,

        a)  if p < k , then kth smallest element is to the right of the pivot , then recursively to find the ( k-p ) th smallest element in the right subarray which is the kth smallest element in the whole array.

        b)  If p < k , then kth smallest element is to the left of the pivot , then recursively to find the kth smallest element in the left subarray which is the kth smallest element in the whole array.

 

Like quick sort, the performance depends on how you choose the pivot. For details , you can refer to : http://seanzhou.iteye.com/blog/1820426.  The following codes implement the randomized pivot choosing whose expected time is O(n) and the medium of medium pivot choosing whose worst time is O(n).

 

The suffle method in the following codes is to do a random suffle of the orginal array, you can refer to :http://seanzhou.iteye.com/blog/1770403

 

public class KSmallestC {

	
	
	public static void main(String[] args) {
		assertEquals(new int[]{1,2,3,4}, getKSmallestByRandomPivot(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 4));
        assertEquals(new int[]{1,2,3,4}, getKSmallestByRandomPivot(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}, 4));
        assertEquals(new int[]{21,22,14,18,9}, getKSmallestByRandomPivot(new int[]{27, 14, 18, 22, 21, 91, 33, 36, 42, 78 , 9, 65, 101, 29}, 5));
        
        assertEquals(new int[]{1,2,3,4}, getKSmallestByMediumPivot(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 4));
        assertEquals(new int[]{1,2,3,4}, getKSmallestByMediumPivot(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}, 4));
        assertEquals(new int[]{21,22,14,18,9}, getKSmallestByMediumPivot(new int[]{27, 14, 18, 22, 21, 91, 33, 36, 42, 78 , 9, 65, 101, 29}, 5));
	}
	
	private static int[] getKSmallestByRandomPivot(int[] arr, int k ) {
		Selector s = new PartitionSelector(arr, new RandomPivotChooser());
		s.select(k);
		int[] result = new int[k];
		System.arraycopy(arr, 0, result, 0, k);
		return result;
	}
	
	private static int[] getKSmallestByMediumPivot(int[] arr, int k ) {
		Selector s = new PartitionSelector(arr, new MediumOfMediumChooser());
		s.select(k);
		int[] result = new int[k];
		System.arraycopy(arr, 0, result, 0, k);
		return result;
	}

	private static void assertEquals(int[] standard, int[] result) {
		Arrays.sort(standard);
		Arrays.sort(result);
		assert Arrays.equals(standard, result);
		
	}
	
    public interface Selector {
    	int select( int index );
    }
    
    public static class PartitionSelector implements Selector{
    	private int[] arr;
		private PivotChooser chooser;

		public PartitionSelector (int[] arr , PivotChooser chooser){
    		this.arr = arr;
    		this.chooser = chooser;
    		chooser.initialize(arr);
    				
    		
    	}

		@Override
		public int select(int index) {
			if (index < 0 && index >= arr.length) throw new IllegalArgumentException("Index out of boundary");
			int end = arr.length;
			int start = 0;
			int pivotIndex = chooser.choosePivot(start, end);
			pivotIndex = partition(start, end, pivotIndex);
			while (pivotIndex != index) {
				if( pivotIndex > index ) {
					end = pivotIndex;
					pivotIndex = chooser.choosePivot(start, end);
					pivotIndex = partition(start, end, pivotIndex);
					
				} else {
					start = pivotIndex + 1;
					pivotIndex = chooser.choosePivot(start, end);
					pivotIndex = partition(start, end, pivotIndex);
				}
			}
			
			return arr[index];
		}
		
		private int partition(int start, int end , int pivotIndex){
			//swap with the partition element with the first one
			int temp = arr[start];
			arr[start] = arr[pivotIndex];
			arr[pivotIndex] = temp;
			int pivot = arr[start];
			int i=start+1,j=end-1;
			while( i <= j ) {
				while ( i <= j && arr[i] <= pivot ) i ++;
				if (i > j) break;
				while (arr[j] > pivot ) j--;
				if ( i > j) break;
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
			i--;
			arr[start] = arr[i];
			arr[i] = pivot;
			return i;
			
		}
		
		
    }
	
	
	
	
	public static class RandomPivotChooser implements PivotChooser{

		private int[] arr;
		private boolean init;

		
		private void shuffle() {
			Random random = new Random();
			int temp, j;
			for ( int i = 1 ; i < arr.length ; i ++ ) {
				j = random.nextInt(i+1);
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		
		@Override
		public int choosePivot(int start, int end) {
			if (! init )  throw new IllegalStateException("Pivot Chooser not initialized!");
			if ( start >= end ) throw new IllegalArgumentException("end should bigger than start!");
			if ( end > arr.length ) throw new IllegalArgumentException("end should not bigger than arry length!");
			return start;
		}

		@Override
		public void initialize(int[] arr) {
			this.arr = arr;
			shuffle();
			this.init = true;
			
		}
		
	}
	
	public static class MediumOfMediumChooser implements PivotChooser{

		private int[] arr;
		private boolean init;
		
		@Override
		public int choosePivot(int start, int end) {
			if ( start >= end ) throw new IllegalArgumentException("end should bigger than start!");
			if ( end > arr.length ) throw new IllegalArgumentException("end should not bigger than arry length!");
			if (! init )  throw new IllegalStateException("Pivot Chooser not initialized!");
            if ( end - start <= 2) {
            	return start;
            }
			
			// sort elements in each block
			int BLOCK_SIZE = 5;
			int i = BLOCK_SIZE;
			int num = 1;
			for ( ; i < end ; i += BLOCK_SIZE , num ++) {
				insertionSort(i - BLOCK_SIZE, i);
			}
			i -= BLOCK_SIZE;
			insertionSort(i, end);

			// choose medium of each group
			int medium = BLOCK_SIZE/2;
			int[] mediums = new int[num];
			int r = ( i + end ) / 2; // medium item in last block
			i = 0 ;
			for ( int j = medium; i < num - 1 ; j += BLOCK_SIZE, i ++ ) {
				mediums[i] = arr[j];
			}
			mediums[i] = arr[r];
			
			
			
			Selector selector = new PartitionSelector(mediums, new MediumOfMediumChooser());
			int pivot = selector.select(num/2);
			for ( i = start; i < end; i ++) {
				if ( arr[i] == pivot) return i;
			}
			
			throw new IllegalStateException("Medium of Medium didn't find a correct pivot!");
		}


		@Override
		public void initialize(int[] arr) {
			this.arr = arr;
			this.init = true;
			
		}
		
		private void insertionSort(int start, int end) {
			int temp;
			for ( int i = start + 1; i < end ; i ++ ) {
		       for ( int j = i ; j > 0 ; j --) {
		    	   if ( arr[j] < arr[j-1] ) {
		    		  temp = arr[j];
		    		  arr[j] = arr[j-1];
		    		  arr[j-1] = temp;
		    	   } else {
		    		   break;
		    	   }
		       }
			}
		}
		
	}
	
	public interface PivotChooser{
		//return the index of the new pivot
		int choosePivot(int start, int end);
		void initialize(int[] arr);
	}

}

 

0
0
分享到:
评论

相关推荐

    Finding Top-k Shortest Simple Paths with Diversity.pptx

    Finding Top-k Shortest Paths with Diversity 在计算机科学和信息技术领域中,寻找 Top-k 最短简单路径问题是一个经典的问题。该问题的应用非常广泛,例如在路线规划、交通导航、物流等领域都有重要的实践价值。本...

    Finding Top-k Min-Cost Connected Trees in Databases2007

    标题 "Finding Top-k Min-Cost Connected Trees in Databases 2007" 指出了这篇论文的核心研究问题,即在数据库中寻找最小成本的前k个连通树。从标题可以推导出以下几点: 1. **数据库**:数据库技术是现代信息系统...

    finding a majority among n votes.pdf

    finding a majority among n votes.pdffinding a majority among n votes.pdffinding a majority among n votes.pdffinding a majority among n votes.pdfv

    Learning the Kernel and Finding Performance Problems with KFI

    标题与描述:“学习内核与使用KFI查找性能问题” 在深入探讨KFI(Kernel Function Instrumentation)如何帮助我们理解Linux内核并检测性能瓶颈之前,让我们先对这个主题有一个全面的理解。 ### KFI:内核函数仪器...

    edge_finding_matlab边缘寻找_

    "edge_finding_matlab边缘寻找_"这个标题所指的是使用MATLAB进行图像边缘检测的过程。下面我们将深入探讨这一主题。 边缘检测的主要目的是将图像从二维空间转化为一维边缘描述,从而简化图像并突出重要的特征。...

    kuka_SeamTech_Finding中文说明书--视觉探寻.pdf

    SeamTech Finding是库卡系统中一款集成视觉探寻功能的软件,用于工业机器人在进行焊接、装配等任务时,通过视觉系统找到焊接缝隙等特征的位置。接下来,将详细介绍SeamTech Finding软件的主要知识点。 ### 1. ...

    论文翻译:On Finding Socially Tenuous Groups for Online Social Networks

    论文翻译:On Finding Socially Tenuous Groups for Online Social Networks。现有的寻找社会群体的研究主要集中在社交网络中的密集子图。然而,寻找社会脆弱的群体也有许多重要的应用。在本文中,我们引入了K三角的...

    Matlab安装Error finding installer class解决方法

    ### Matlab安装Error finding installer class解决方法 #### 问题背景及表现 在安装特定版本的Matlab(例如R2009b、R2010b等)时,可能会遇到一个名为“Error finding installer class”的错误。这个错误通常出现在...

    Finding Metric Structure in Information Theoretic Clustering

    《Finding Metric Structure in Information Theoretic Clustering》一文由Kamalika Chaudhuri和Andrew McGregor共同撰写,深入探讨了使用Kullback-Leibler(简称KL)散度作为距离度量进行聚类的问题。 ### 1. KL...

    finding-lungs-in-ct-data.zip

    "finding-lungs-in-ct-data.zip" 文件集合显然与CT图像处理相关,特别是关注肺部的分析。这个压缩包包含了几个关键文件,它们提供了用于肺部分割和体积识别的数据和结果。 首先,`lung_stats.csv` 文件很可能是记录...

    Finding People in Images and Videos

    Finding People in Images and Videos,dalal大神的毕业论文130多页,我打印出一部分看过,理解hog很有用,光流部分还没看。还有另一个人毕业论文,放这里,怕自己以后找不到

    root-finding.rar_ROOT_root finding_root-finding

    标题中的"root-finding.rar_ROOT_root finding"暗示了这是一个关于根查找算法的资料包,而描述提到了三种方法:二分法、最近邻法和错点法。 **二分法**(Bisection Method)是最基础且最直观的根查找算法之一。它...

    FINDING STRUCTURE WITH RANDOMNESS.pdf

    3. 对于那些因太大而不能完全加载到快速内存中的矩阵,随机化技术仅需要常数次遍历数据,而传统算法需要O(k)次遍历。实际上,有时可以仅用一次数据遍历就能完成矩阵近似。 文章还讨论了低秩矩阵近似的模型问题,即...

    A Unified Method for Finding Impossible Differentials of

    本文介绍了一种系统化的方法——统一不可能差分查找方法(Unified Impossible Differential finding method, UID-method),用于高效地寻找各种块密码结构中的不可能差分。这种方法相较于先前由Kim等人提出的U-...

    the Big Data Tidal Wave, Finding Opportunities in Huge Data Streams

    ( Wiley Taming the Big Data Tidal Wave, Finding Opportunities in Huge Data Streams with Advanced Analytics (2012).pdf )

    Finding Lungs in CT Data – CT 影像数据集.torrent

    Finding lungs in CT 是基于肺部 CT 影像分割处理的数据集,其包含一系列 CT 影像中对肺部影像的分割,并以此识别和估计肺部容积量。 该数据集包含 4 名患者的数据,以 nifti 格式的图像和分段肺面罩为主,由 ...

    Finding scientific topics.pdf

    文档标题和描述均表明文章主要探讨了使用概率主题模型来发现科学文献中的话题。这种方法被称为“发现科学话题”,具体来说,文章介绍了由Blei、Ng和Jordan提出的文档生成模型,并利用贝叶斯模型选择方法和马尔可夫链...

    An optimal algorithm for finding segment intersections

    Balaban在前人研究的基础上,提出了一种新的确定性算法,该算法不仅在时间复杂度上达到了O(N logN + K),而且空间复杂度仅为O(N),其中K表示交点的数量。这一成果标志着在解决线段交点问题时,时间和空间复杂度的最...

    A Recommender System for Finding Passengers and Vacant Taxis

    A Recommender System for Finding Passengers and Vacant Taxis

Global site tag (gtag.js) - Google Analytics