算法題解之尋找最大的k個數

        一般看到尋找最大的k個數的題目，我們第一想法便是先使用降序排序，然後取前k個即可，這種方法确實是比較正常的，一般情況下也是可行的，但是如果資料十分龐大，則會影響使得建立的數組記憶體溢出等等。是以，需要對相關算法思路進行優化，以下是幾種不同解法。通過不同解法比較進而更了解該算法題。

1.簡單排序法

        從n個數中直接先排序，然後求最大的k個，進而擷取最大的k個數。代碼如下：

package knum;
import java.util.*;
public class GeneralSort {
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		int[] data=new int[n];
		for(int i=0;i<n;i++)
			data[i]=sc.nextInt();
		Arrays.sort(data);
		for(int j=0;j<k-1;j++)
		{
			System.out.print(data[--n]+" ");
		}
		System.out.print(data[--n]);
		
	}

}
           

測試結果如下：

10 3
1 5 7 4 8 20 2 15 9 10
20 15 10
           

        以上采用的是系統自帶的排序，總的求解時間複雜度為O(n*logn+k)，近似于O(n*logn)。至于排序可以換成快排或者歸并排序來進行實作。

2.建立最小堆實作

        以上是對所有資料都進行排序，則進行排序的資料的量可能非常大，如果k的值遠小于n，則會影響效率。是以，可以借鑒堆排序的方法，通過維護最小堆來進行保留k個最大值。該方法的思路是：首先先讀取k個數字，對這k個數字進行建立最小堆，将最小的數放到堆頂，然後再讀取第k+1個數，比較堆頂與該值，取較大值。然後重複上述的操作，留下最後k個數即為需要求的k個最大值。時間複雜度為O(nlogk)。這種方法好處在于不必擔心數組記憶體的溢出以及時間複雜度較一般排序法也能稍作優化。實作代碼如下：

package knum;
import java.util.*;
public class HeapSort {  
	
	public static void swap(int[] data,int i,int j)  
    {  
        if(i==j)  
            return;  
        data[i]=data[i]+data[j];  
        data[j]=data[i]-data[j];  
        data[i]=data[i]-data[j];  
    }  
    public static int[] heapSort(int[] data,int[] A,int k)  
    {  
        for(int i=0;i<A.length-k;i++)//控制堆大小。  
        {  
            //每次周遊建立最小堆，并且将堆頂元素與給定數組的數字按序逐個比較，若小于相應元素，則替換堆頂元素。  
            createMinHeap(data,k-1);//堆化  
            if(data[0]<A[k+i])
            	data[0]=A[k+i];
            print(data);  
        }  
        return data;  
    }  
      
    public static void createMinHeap(int[] data,int lastIndex)  
    {  
        for(int i=(lastIndex-1)/2;i>=0;i--)  //先找到最後一個節點的雙親節點，然後依次往回周遊，
        {									//并在過程中重新通路目前節點的子節點，目的就是将最小值移到雙親位置，依次往上，直到最小值到達堆頂
            //儲存目前正在判斷的節點  
            int k=i;  
            //若目前節點存在  
            while(2*k+1<=lastIndex)  
            {  
                //smallerIndex總是記錄較小節點的值,先指派為目前判斷節點的左子節點  
                int smallerIndex=2*k+1;  
                if(smallerIndex<lastIndex) //判斷是否存在右子節點
                {  
                    //若右子節點存在，否則此時smallerIndex應該等于lastIndex  
                    if(data[smallerIndex]>data[smallerIndex+1])  
                    {  
                        //若右子節點值比左子節點值小，則smallerIndex記錄的是右子節點的值  
                    	smallerIndex++;  
                    }  
                  
                }  
                if(data[k]>data[smallerIndex])  
                {  
                    //若目前節點值比子節點最小值大，則交換兩者的值，交換後将smallerIndex值賦給k，相當于将最小值往堆頂推
                    swap(data,k,smallerIndex);  
                    k=smallerIndex;  
                }  
                else  
                    break;  
            }  
        }  
    }  
      
    public static void print(int[] data)  
    {  
        for(int i=0;i<data.length;i++)  
            System.out.print(data[i]+" ");  
        System.out.println();  
    }  
      
    public static void main(String[] args)  
    {  
    	Scanner sc=new Scanner(System.in);
    	int n=sc.nextInt();
    	int k=sc.nextInt();
    	int[] A=new int[n];
    	int[] data=new int[k];
    	for(int j=0;j<n;j++)
    	{
    		A[j]=sc.nextInt();
    	}
    	
    	for(int j=0;j<k;j++)
    	{
    		data[j]=A[j];
    	}
        
        int[] ans=heapSort(data,A,k);  
        System.out.println("堆排序後的序列：");  
        for(int j=0;j<ans.length;j++)  
            System.out.print(ans[j]+" ");  
    }  
  
}  
           

測試結果如下：

10 3
1 5 7 4 8 20 2 15 9 10
4 5 7 
8 5 7 
20 8 7 
7 8 20 
15 8 20 
9 15 20 
10 15 20 
堆排序後的序列：
10 15 20