首页 > 试题广场 >

无序数组中最小的k个数

[编程题]无序数组中最小的k个数
  • 热度指数:9069 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

对于一个无序数组,数组中元素为互不相同的整数,请返回其中最小的k个数,顺序与原数组中元素顺序一致。

给定一个整数数组A及它的大小n,同时给定k,请返回其中最小的k个数。

测试样例:
[1,2,4,3],4,2
返回:[1,2]

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

return sorted(sorted(A)[:k], key=A.index)
编辑于 2017-09-12 12:13:18 回复(3)
先用快速排序的思想找到第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;
    }
};

发表于 2016-09-05 16:30:34 回复(0)
这道题测试数据有问题,首先给定数组的大小不一定是真正的大小,调用函数时直接将n重新做的赋值=A.size(),通过率从百分之30到了百分之96多,还有个测试实例没有通过,这个实例数组大小应该是83, 第31个数是18897,而且 测试数据只有一个15539,答案输出却有两个15539

测试用例:
[16623,11263,27224,1374,28243,12025,35595,23825,30591,17911,13499,33856,17145,41898,25686,37261,4025,27318,5327,27685,19662,15902,34683,2807,19737,29773,20816,30378,6204,7959,11453,42194,40811,38037,23309,27252,36361,26453,22951,24705,25188,37521,12909,40001,39741,9820,8272,19383,27274,14974,24726,39710,1941,32660,14351,23254,41058,20144,10661,4896,39424,29002,31492,32478,33392,18897,6966,12929,23049,8438,41087,3078,15539,20410,34508,38646,22596,9373,21788,14473,33444,785,25974],84,31

对应输出应该为:

[16623,11263,1374,12025,17911,13499,17145,4025,5327,15902,2807,6204,7959,11453,12909,9820,8272,14974,1941,15539,14351,10661,4896,6966,12929,8438,3078,15539,9373,14473,785]

你的输出为:

[16623,11263,1374,12025,17911,13499,17145,4025,5327,15902,2807,6204,7959,11453,12909,9820,8272,14974,1941,14351,10661,4896,18897,6966,12929,8438,3078,15539,9373,14473,785]
发表于 2016-04-26 22:17:27 回复(4)
//堆排序
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;
    }
};

发表于 2016-08-25 18:27:13 回复(0)
对于本题应首先明确一点:需要保留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;
    }
}

发表于 2017-04-20 22:00:05 回复(0)
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;

    }

发表于 2018-03-13 23:11:10 回复(0)
/*
分析:
本题中的难点在于返回的最小的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

发表于 2017-08-19 23:33:25 回复(0)
使用BFPRT算法,时间复杂度O(N)

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

发表于 2017-08-08 19:41:34 回复(1)
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;
    }
};

发表于 2017-04-27 11:38:58 回复(2)

//我的思想是转化成删除较大的元素来,每次删除n-k个较大元素,那么就不会
//使元素位置变了,最开始想着排序的捷径,然后仔细发现了问题是变化后顺序不变
class KthNumbers {
public:
    vector<int> findKthNumbers(vector<int> A, int n, int k) {
     
      
        int num;
        for(int d=0;d<n-k;d++)
{           num=*A.begin();
            auto current=A.begin();
            for(auto it=A.begin();it!=A.end();it++)
       {
           
            if(num<*it){
                num=*it;
            current=it;
            }
        }

        current=A.erase(current);
    }
        return A;
    }
};
发表于 2016-06-30 22:23:57 回复(0)
# -*- 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

发表于 2016-05-14 06:38:23 回复(2)
import java.util.*;

public class KthNumbers {
      public static int[] findKthNumbers(int[] A, int n, int k) {
        int[] num=new int[n];
        for(int i=0;i<n;i++){
            num[i]=A[i];
        }
        Arrays.sort(num);
        int[] min=new int[k];
        int index=0;
        int number=num[k-1];
        for(int i=0;i<n;i++){
            if(A[i]<=number){
                min[index]=A[i];
                index++;
            }
        }
        return min;
}
}
java.lang.ArrayIndexOutOfBoundsException: 169
这是为何,我明明没有越界
发表于 2016-04-22 16:13:56 回复(3)
错在那组n = 170的样例了,这道题有两种做法,一个是用partion,另一个是用数据结构(堆或者红黑树)
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;
    }
};

发表于 2016-04-06 01:30:02 回复(0)
有STL就变得很简单了
1、排序
2、找到k大作为基准
3、遍历比较,小于k的输出

    vector<int> findKthNumbers(vector<int> A, int n, int k) {
        vector<int> B = A;
        vector<int> ans;
        sort(B.begin(),B.end());
        for(int i=0;i<A.size();i++)
            if(A[i] <= B[k-1])
            	ans.push_back(A[i]);
        return ans;
    }

发表于 2016-09-02 17:01:45 回复(4)
首先用快速排序的思想找到第K小的元素,然后遍历原数组依次输出小于或等于该元素的值
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;
    }
};
发表于 2016-03-10 21:10:25 回复(7)

基于快排思想划分区域,选取第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;
    }
}
发表于 2022-04-30 20:16:27 回复(0)
汗颜!哥们想到的分治算***改变数组输出顺序,只能暴力拆解,用一个数组接收A,直接排序,得到第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];
    }
}

发表于 2019-04-16 23:10:47 回复(0)
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;
    }
}

发表于 2018-09-26 17:45:16 回复(0)

考虑到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;
    }
};
发表于 2018-09-03 15:12:07 回复(0)
# -*- 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

发表于 2018-08-28 17:08:54 回复(0)