无序数组中最小的k个数

我大python代码只要写在return里面，只需要一行就***：

return sorted(sorted(A)[:k], key=A.index)

先用快速排序的思想找到第K小的数，然后遍历vector,小于等于第k小的数依次加入vector。
class KthNumbers {
public:
    int Partition(vector<int> &A,int start, int end){
        int i=start,j=end,key=A[start];
        while(i<j){
            while(i<j&&A[j]>=key)
                j--;
            A[i]=A[j];
            while(i<j&&A[i]<=key)
                i++;
            A[j]=A[i];
        }
        A[i]=key;
        return i;
    }
    int findKthMin(vector<int> A,int start, int end, int k){
        int i=Partition(A,start,end);
        if(i+1==k){
            return A[i];
        }else if(i+1<k){
          	return findKthMin(A,i+1,end,k);  
        }else{
            return findKthMin(A,start,i-1,k);
        }
    }
    vector<int> findKthNumbers(vector<int> A, int n, int k) {
        int index=findKthMin(A,0,n-1,k);
        vector<int> vec;
        for(int i=0;i<n&&vec.size()<=k;i++){
            if(A[i]<=index)
                vec.push_back(A[i]);
        }
        return vec;
    }
};

//堆排序
class KthNumbers {
public:
    vector<int> findKthNumbers(vector<int> A, int n, int k) {
        // write code here
        vector<int> AA=A;
        int cc=k;
        make_heap(AA.begin(),AA.end(),greater<int>());
        set<int> nset;
        while(cc--)
            {
            pop_heap(AA.begin(),AA.end(),greater<int>());
            nset.insert(AA.back());
            AA.pop_back();
        }
        vector<int>ans;
        
        for(auto i:A)
            {
            if(nset.count(i))ans.push_back(i);
            if(ans.size() == k)break;
        }
        return ans;
    }
};

对于本题应首先明确一点：需要保留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;
    }
}

O(Nlogk)复杂度解法，O（N）复杂度的BFPRT算法，太复杂，不造次了；
public int[] findKthNumbers(int[] arr, int n, int k) {

        if (k < 1 || k > arr.length) {
            return arr;
        }
        int[] kHeap = new int[k];
        for (int i = 0; i < k; i++) {
            heapInsert(kHeap, arr[i], i);
        }

        for (int i = k; i < arr.length; i++) {
            if (arr[i] < kHeap[0]) {
                kHeap[0] = arr[i];
                heapify(kHeap, 0, k);
            }
        }
        return kHeap;
    }

    /*
     * 找到无序数组中最小的K个数 heapInsert建堆
     */
    public static void heapInsert(int[] arr, int value, int index) {
        arr[index] = value;
        while (index != 0) {
            int parent = (index - 1) / 2;
            if (arr[parent] < arr[index]) {
                swap(arr, parent, index);
                index = parent;
            } else {
                break;
            }
        }

    }

    /*
     * 找到无序数组中最小的K个数 heapify 调整堆
     */
    public static void heapify(int[] arr, int index, int heapSize) {

        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int largest = index;
        while (left < heapSize) {

            if (arr[left] > arr[index]) {
                largest = left;
            }
            if (right < heapSize && arr[right] > arr[largest]) {
                largest = right;
            }
            if (largest != index) {
                swap(arr, largest, index);
            } else {
                break;
            }

            index = largest;
            left = index * 2 + 1;
            right = index * 2 + 2;
        }
    }
    
    /**
     * 交换两个数 ij
     * 
     * @param numbers
     * @param i
     * @param j
     */
    private static void swap(int[] numbers, int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;

    }

/*
分析：
本题中的难点在于返回的最小的k个数，顺序需要与原数组中元素顺序一致，比较艰难。
方法1：复制一个数组B，对数组B进行归并排序，然后比较数组A和B，当匹配上时，复制到返回数组C中。
或者直接找到Kth数字，作为基准找到所有小于等于的数值，这种方法的有一个明显的弊端:
当数组A中最小的Kth数字有多个重复值，且在原数组中，在重复数字后有更小的数字，
例如输入：9 1 5 4 4 10 2 | 7 | 3，按照该方法的输出为1 4 4 得到错误的答案。
时间复杂度：O(nlgn)+nk+k
空间复杂度：n+k
代码如下：
class KthNumbers {
public:
    vector<int> findKthNumbers(vector<int> A, int n, int k) {
        // write code here
        vector<int> B = A;
        sort(B.begin(),B.end());
        vector<int> result;
        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < k;j++)
            {
                if(A[i] == B[j])
                result.push_back(A[i]);
            }
        }
        return result; 
    }
};
运行时间：4ms
占用内存：496k
方法2：由于需要按照原顺序输出最小的k个数，所以可以考虑删除最大的n-k个值，那么剩下的k个最小的值自然是按照原顺序的。
时间复杂度：nk
空间复杂度：忽略不计
代码如下：
class KthNumbers {
public:
    vector<int> findKthNumbers(vector<int> A, int n, int k) {
        // write code here
        //int count = n - k;
        while((int)A.size()>k)
        {
            int temp = A[0];
            int max_index = 0;
            for(int i = 1;i < (int)A.size();i++)
            {
                if(temp < A[i])
                {
                    temp = A[i];
                    max_index = i;
                }
            }
            A.erase(A.begin()+max_index);
        }
        return A;    
    }
};
运行时间：4ms
占用内存：504k

import java.util.*;

public class KthNumbers {
    public int[] findKthNumbers(int[] A, int n, int k) {
        // write code here
        if (k < 1 || k > n) {
            return A;
        }
        int kthMin = getKthMinByBFPRT(A, k);    // 使用BFPRT算法求得第k小的数，O(N)
        int[] kMins = new int[k];               // 下面遍历一遍数组，利用第k小的数找到最小的k个数，O(N)
        int index = 0;
        for (int i = 0; i < n && index < k; i++) {
            if (A[i] <= kthMin) {              // 小于第k小的数，必然属于最小的k个数
                kMins[index++] = A[i];
            }
        }
        return kMins;
    }
    
    /**
     * 使用BFPRT算法求第k小的数
     *
     * @param arr
     * @param k
     * @return
     */
    public static int getKthMinByBFPRT(int[] arr, int k) {
        int[] arrCopy = copyArray(arr); // 在得到第k小的数之后还要遍历一遍原数组，所以并不直接操作原数组
        return select(arrCopy, 0, arrCopy.length - 1, k - 1);   // 第k小的数，即排好序后下标为k-1的数
    }

    /**
     * 拷贝数组
     *
     * @param arr
     * @return
     */
    public int[] copyArray(int[] arr) {
        int[] arrCopy = new int[arr.length];
        for (int i = 0; i < arrCopy.length; i++) {
            arrCopy[i] = arr[i];
        }
        return arrCopy;
    }


    /**
     * 在数组arr的下标范围[begin, end]内，找到排序后位于整个arr数组下标为index的数
     *
     * @param arr
     * @param begin
     * @param end
     * @param index
     * @return
     */
    public int select(int[] arr, int begin, int end, int index) {
        if (begin == end) {
            return arr[begin];
        }
        int pivot = medianOfMedians(arr, begin, end);   // 核心操作：中位数的中位数作为基准
        int[] pivotRange = partition(arr, begin, end, pivot);   // 拿到分区后中区的范围
        if (index >= pivotRange[0] && index <= pivotRange[1]) { // 命中
            return arr[index];
        } else if (index < pivotRange[0]) {
            return select(arr, begin, pivotRange[0] - 1, index);
        } else {
            return select(arr, pivotRange[1] + 1, end, index);
        }
    }

    /**
     * 选基准
     *
     * @param arr
     * @param begin
     * @param end
     * @return
     */
    public int medianOfMedians(int[] arr, int begin, int end) {
        int num = end - begin + 1;
        int offset = num % 5 == 0 ? 0 : 1;      // 5个成一组，不满5个的自己成一组
        int[] mArr = new int[num / 5 + offset]; // 每组的中位数取出构成中位数数组mArr
        for (int i = 0; i < mArr.length; i++) {
            int beginI = begin + i * 5;
            int endI = beginI + 4;
            mArr[i] = getMedian(arr, beginI, Math.min(endI, end));
        }
        // 求中位数数组mArr的中位数，作为基准返回
        return select(mArr, 0, mArr.length - 1, mArr.length / 2);
    }

    /**
     * 在数组arr的下标范围[begin, end]内，找中位数，如果元素个数为偶数则找下中位数
     *
     * @param arr
     * @param begin
     * @param end
     * @return
     */
    public int getMedian(int[] arr, int begin, int end) {
        insertionSort(arr, begin, end);
        int sum = begin + end;
        int mid = (sum / 2) + (sum % 2);
        return arr[mid];
    }

    /**
     * 这里仅用于对一组5个数进行插入排序，时间复杂度O(1)
     *
     * @param arr
     * @param begin
     * @param end
     */
    public void insertionSort(int[] arr, int begin, int end) {
        for (int i = begin + 1; i <= end; i++) {
            int get = arr[i];
            int j = i - 1;
            while (j >= begin && arr[j] > get) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = get;
        }
    }

    /**
     * 优化后的快排partition操作
     *
     * @param arr
     * @param begin
     * @param end
     * @param pivot
     * @return 返回划分后等于基准的元素下标范围
     */
    public int[] partition(int[] arr, int begin, int end, int pivot) {
        int small = begin - 1;     // 小区最后一个元素下标
        int big = end + 1;         // 大区第一个元素下标
        int cur = begin;
        while (cur < big) {
            if (arr[cur] < pivot) {
                swap(arr, ++small, cur++);
            } else if (arr[cur] > pivot) {
                swap(arr, --big, cur);
            } else {
                cur++;
            }
        }
        int[] range = new int[2];
        range[0] = small + 1;      // 中区第一个元素下标
        range[1] = big - 1;        // 中区最后一个元素下标
        return range;
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
} 

class KthNumbers {
public:
    vector<int> findKthNumbers(vector<int> A, int n, int k) {
        // write code here
        vector<int> temp(A);
        sort(temp.begin(), temp.end());
        vector<int> result;
        for(int i = 0; i < n; i ++){
            if(A[i] < temp[k])
                result.push_back(A[i]);
        }
        return result;
    }
};

# -*- coding:utf-8 -*-
class KthNumbers:
    def findKthNumbers(self, A, n, k):
        # write code here
        for i in range(n-k):
            A.remove(max(A))
        return A

class KthNumbers {
    int partion(vector<int> &A, int left, int right){
        int pivot = A[right];
        int index = left - 1;
        for(int i = left; i < right; ++ i){
            if(A[i] < pivot){
				++index;
                swap(A[index], A[i]);
            }
        }
        ++ index;
        swap(A[index], A[right]);
    	return index;
    }
    
public:
    vector<int> findKthNumbers(vector<int> A, int n, int k) {
        // write code here
        vector<int> result;
        if(n == 0) return result;
        vector<int> num(A);
        int left = 0;
        int right = n - 1;
        int index = partion(num, left, right);
            
        while(index != k - 1){
            if(index > k - 1) {
                right = index - 1;
                index = partion(num, left, right);
            }
            
            if(index < k - 1) {
                left = index + 1;
                index = partion(num, left, right);
            }
        }
        
        for(int i = 0; i < n; ++ i)
            if(A[i] < num[k])
        	result.push_back(A[i]);
        
        return result;
    }
};

class KthNumbers {
public:
    int quickFind(vector<int> &arr, int start, int end, int target) {
        
        if(start == end) {
            return arr[start];
        }
        int current = start;
        int left = start + 1;
        int right = end;
        while(left <= right) {
            while(left <= right && arr[right] >= arr[current]) {
                right--;
            }
            if(left <= right) {
                int tmp = arr[right];
                arr[right] = arr[current];
                arr[current] = tmp;
                current = right;
            }
            while(left <= right && arr[left] <= arr[current]) {
                left++;
            }
            if(left <= right) {
                int tmp = arr[left];
                arr[left] = arr[current];
                arr[current] = tmp;
                current = left;
            }
        }
        if(current < target) {
            return quickFind(arr, current + 1, end, target);
        }
        if(current > target) {
            return quickFind(arr, start, current - 1, target);
        }
        return arr[current];
    }
    vector<int> findKthNumbers(vector<int> A, int n, int k) {
        // write code here
        vector<int> res;
        if(k > n || n < 1) {
            return res;
        }
        res.assign(A.begin(), A.end());
        int val = quickFind(res, 0, n - 1, k - 1);
        res.clear();
        for(int i = 0; i < A.size(); i++) {
            if(A[i] <= val) {
                res.push_back(A[i]);
            }
        }
        return res;
    }
};

基于快排思想划分区域，选取第k小的数字，然后遍历原数组取比它小的所有数字

import java.util.*;
public class KthNumbers {
    public int[] findKthNumbers(int[] A, int n, int k) {
        // write code here
        int[] res = new int[k];
        int[] tmp = A.clone();
        int left =0,right=A.length-1,target=0;
        while(true){
            int idx = partion(A,left,right);
            if(idx+1 == k){
                target = A[idx];
                break;
            }else if(idx+1<k){
                left = idx+1;
            }else{
                right = idx-1;
            }
        }
        for(int i=0,j=0;i<tmp.length && j<k;i++){
            if(tmp[i]<=target){
                res[j++]=tmp[i];
            }
        }
        return res;
    }
    public int partion(int[] nums,int i,int j){
        int pviot = nums[i];
        int left =i,right=j;
        while(left < right){
            while(left=pviot)right--;
            //if(left<right)nums[left]=nums[right];
            while(left<right && nums[left]<=pviot)left++;
            if(left<right){
                swap(nums,right,left);
            }
            //if(left<right)nums[right]=nums[left];
        }
        swap(nums,left,i);
        //nums[left]=pviot;
        return left;
    }

     private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
    }
}

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;
    }
}

考虑到n可能比较大，利用priority_queue维护k个最小的数值，只需要占用O(k)的空间。（网易游戏电面就说了这道题目，限制是内存太小，不能同时放置n个数）。

class KthNumbers {
public:
    vector<int> findKthNumbers(vector<int> A, int n, int k) {
        // write code here
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < n; i++){
            pq.push({ A[i], i });
            if (i >= k) pq.pop();
        }
        vector < pair<int, int>> tmp;
        while (!pq.empty()){
            tmp.push_back(pq.top());
            pq.pop();
        }
        sort(tmp.begin(), tmp.end(), [](const pair<int, int>& a, const pair<int, int>& b){
            return a.second < b.second;
        });
        vector<int> res;
        for (auto& t : tmp){
            res.push_back(t.first);
        }
        return res;
    }
};

# -*- coding:utf-8 -*-
class KthNumbers:
    def findKthNumbers(self, A, n, k):
        B=sorted(A)#对A进行排序
        ans=filter(lambda x:x<=B[k-1],A)#过滤出小于等于第k大的数字
        return ans