无序数组中最小的k个数

import java.util.*;

public class KthNumbers {
    public int[] findKthNumbers(int[] A, int n, int k) {
        // write code here
        int[] arr = new int[k];
        int m = GetK(A,k);
        for(int i=0,j=0;i<n&&j<k;i++){
            if(A[i]<=m){
                arr[j] = A[i];
                j++;
            }
        }
        return arr;
    }
    public static int GetK(int[] A,int k){
        int[] tmp = new int[A.length];
        for(int i=0;i<A.length;i++){
            tmp[i] = A[i];
        }
        Arrays.sort(tmp);
        return tmp[k-1];
    }
}

public class KthNumbers {
    public static int[] findKthNumbers(int[] A, int n, int k) {
        int count = n - k;
        int length = A.length;
        while (count > 0) {
            int maxNumberIndex = 0;
            int i;
            for (i = 1; i < length; i++) {
                if (A[maxNumberIndex] < A[i]) {
                    maxNumberIndex = i;
                }
            }
            for (int j = maxNumberIndex; j < length - 1; j++) {
                A[j] = A[j + 1];
            }
            length--;
            count--;
        }
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            result[i] = A[i];
        }
        return result;
    }
}

• 复制一个原数组命名为CA
• 将CA升序排序，找到临界值CA[k-1]
• 遍历原数组A，将小于等于CA[k-1]的数放到一个新数组中，over.

  public static int[] findKthNumbers(int[] A, int n, int k) {
        int[] CA = new int[n];
        System.arraycopy(A, 0, CA, 0, n);
        Arrays.sort(CA);
        int[] min = new int[k];
        int index = 0;
        int number = CA[k - 1];
        for (int i = 0; i < n; i++) {
            if (A[i] <= number) {
                min[index] = A[i];
                index++;
            }
        }
        return min;
    }
  

import java.util.*;

public class KthNumbers {
    public int[] findKthNumbers(int[] A, int n, int k) {
    	int B[] = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            B[i] = A[i];
        }
        
    	java.util.Arrays.sort(A);
        
        int kth = A[k-1];
        
        int[] result = new int[k];
        int index = 0;
        
        for(int i=0; i< B.length; i++){
            if( B[i] <= kth){
                result[index] = B[i];
                index++;
            }
        }
        
        return result;
    }
}

对于本题应首先明确一点：需要保留k个较小的元素，那也就意味着可以删除除n-k个较大的元素。
具体实现代码如下：

public class KthNumbers {
        public static int[] findKthNumbers(int[] A, int n, int k) {
        // write code here
    	int count=n-k;//要删除的元素数量
    	int LENGTH=A.length;//实际数组中的元素个数
    	while(count>0){
      	//删除当前数组中最大的元素
    	int max_index=0;//记录最大元素的下标
    	int i;
    	for(i=1;i<LENGTH;i++){//寻找最大元素并记录其在数组中的下标
    		if(A[max_index]<A[i]){
    			max_index=i;
    		}
    	}
    	//删除当前最大元素即max_index
    	for(int j=max_index;j<LENGTH-1;j++){
    		A[j]=A[j+1];
    	}
    	LENGTH--;//注意删除后数组的个数要减一
    	count--;   	
    	}//end while****************
    	
        int res[] = new int[LENGTH];//结果集数组
    	for(int i=0;i<LENGTH;i++){//当删除完元素后只需将保留下的k个元素赋值到结果数组中
    		res[i]=A[i];
    	}
    	return res;
    }
}