`

查找最小的k个元素

阅读更多
题目:输入n个整数,输出其中最小的k个。

例如:输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4


思路:用一个k的容器,先放入K个数,然后接下来总是把最大数给踢出去。

用大顶堆,或者红黑树,大顶堆,大顶堆在O(1)得到已有的k个数字中的最大值,但需要O(logk)时间完成删除以及插入操作。红黑树通过把结点分为红、黑两种颜色并根据一些规则确保树是平衡的,从而保证在红黑树中查找、删除和插入操作都只需要O(logk)

public void getMinK(int[] arr,int k){
   List<Integer> stack= new ArrayList<Integer>(); //里面放最小的k个数
   for(int i=0;i<arr.length;i++){
   }

}

-------------------------------------------------------------------------------------------

#include <stdio.h>
//已知(k1,k2……,kn)是堆,试写一个算法将(k1,k2,……,kn,kn+1)调整为堆。
//按此思想写一个从空堆开始一个一个填入元素的建堆算法
//(题示:增加一个k n+1后应从叶子向根的方向调整)
#define length 6
void HeadSort(int a[],int n);
void HeadAdjust(int a[],int s, int m);
void HeadAdjust(int *a,int head, int tail) {  
    int temp;
    temp = a[head];           //若s=2 ,则rc = a[1]
    for ( int j= 2*head; j <= tail; j= 2*j) {
        if( j<tail && a[j]<a[j+1])
            ++j;
        if( temp > a[j])  
            break;
        a[head] = a[j];
        head = j;          
    }
    a[head] = temp;  
//打印*********************
    for(int i = 0 ; i < length; i++) {
            printf("%d ",a[i]);
    }
    printf("/r/n");
  
//打印*********************打印结束
} //    HeadAdjust
void HeadSort(int *a,int n) {
    int i;
    int tmp;
    for( i = length/2  ; i > 0; --i) {
        HeadAdjust(a,i,length);
    }
//打印*********************
    for(i = 0 ; i < length; i++) {
        printf("%d ",a[i]);
    }
    printf("/r/n");
//**********************打印结束
    tmp = a[0];
    a[0] = a[length-1];
    a[length-1] = tmp;
//打印**********************  
    for(i = 0 ; i < length; i++) {
        printf("%d ",a[i]);
    }
    printf("/r/n");
//打印*********************打印结束
    for(i = length-1; i>1; --i) {//////////////
        printf("i's value:%d/n",i);
        HeadAdjust(a,0,i);
        tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;  
    }
    printf("i's value:%d/n",i);
}
int main() {
  
    int n ;
    int a[1000] ;
    printf("Input the Number you want to Sort :");
    scanf("%d",&n);
    printf("Please Input the values :");
    for(int i=0;i<n;++i)
        scanf("%d",&a[i]);//输入时,不能在"%d"内多出任何空格,否则需要多敲一个字符********************Important
    printf("/r/n");
    HeadSort(a,n);
    for(i=0;i<n;++i)
        printf("%d ",a[i]);
    printf("/r/n");
    return fals
分享到:
评论

相关推荐

    查找最小的k个元素-java版

    输出一组元素中的最小的k个元素。例如数据集为:{1、8、3、6、5、4、7、2},则最小的4个数字为1,2,3和4。 【基本要求】 由随机数产生测试数据,测试数据不小于10000个,测试k的不同取值对算法的影响,如k=10、50、...

    算法中最小K元素的选择问题

    在计算机科学中,"算法中最小K元素的选择问题"是一个重要的数据结构和算法主题,它涉及到从一个无序或有序的数组中找到第K小(或大)的元素。这个问题在各种应用场景中都有广泛的应用,比如数据库查询优化、排序算法...

    第k小元素查找C++程序实现

    这个问题的基本目标是从一个未排序或已排序的数组或集合中找出第k个最小的元素。这里我们将深入探讨三种方法来解决这个问题:中位选择法、随机选择查找以及排序查找。 1. **中位选择法**: 中位选择法是一种高效...

    分治算法求最大值与最小值,找最小元素

    3. 计算基准元素所在位置的索引,如果这个索引等于k-1,则基准就是第k个最小元素;如果索引小于k-1,说明第k个最小元素在基准右边的子数组中;如果索引大于k-1,则第k个最小元素在基准左边的子数组中。 4. 递归地在...

    寻找第k小元素 基本算法复习

    创建一个大小为k的最小堆,将数组的前k个元素放入堆中。之后,遍历数组剩余的元素,如果元素小于堆顶元素(即第k小元素),则替换堆顶元素并重新调整堆。最后,堆顶元素即为第k小元素。这种方法的时间复杂度为O(n ...

    Google等公司数据结构+算法面试.pdf

    5. **查找最小k个元素**: 使用最小堆,将前k个元素放入堆中,之后依次与堆顶元素比较,若新元素小于堆顶,则替换并调整堆。最终堆中的k个元素就是最小的k个。 6. **分配计数问题**: 这个问题可以通过计数排序或...

    E软等公司数据结构+算法面试第1-100题汇总

    5. **查找最小k个元素** 快速选择算法可以用来在O(n)平均时间复杂度内找出数组中的最小k个元素。该算法基于快速排序的思想,每次选取一个基准值,将小于基准的元素放到基准左边,大于基准的元素放到右边,然后根据k...

    July整理的100题微软数据结构和算法面试题

    5. **查找最小k个元素**: 快速选择或堆排序是解决这类问题的有效方法。快速选择可以在平均情况下达到O(n)的时间复杂度,堆排序可以保证在最坏情况下也保持O(n log k)的时间复杂度。可以构建一个大小为k的小顶堆,...

    常见:各大公司实习生面试题总汇1

    5. **查找最小k个元素**: 快速选择或堆排序可以解决这个问题。快速选择可以在平均O(n)的时间内找到第k小的元素。堆排序则可以将数组构建成一个最小堆,然后依次取出k个最小元素。 6. **数组分配问题**: 这是一...

    微软等公司数据结构+算法面试第1-100题汇总

    5. **查找最小k个元素**: 快速选择或堆排序可以高效地找到数组中的最小k个元素。快速选择基于快速排序的思想,平均时间复杂度为O(n),最坏情况下为O(n^2),而堆排序始终保证O(n log n)的时间复杂度。 6. **统计...

    微软等公司数据结构及算法面试第1-100题汇总

    5. **查找最小 k 个元素**:可以使用优先队列(堆)来解决,每次取出最小元素并维护堆的大小为 k,最后堆中的 k 个元素即是最小的 k 个数。时间复杂度为 O(n log k)。 6. **统计每个数的出现次数**:可以使用哈希表...

    微软等IT名企经典笔试100题

    5. **查找最小k个元素** 使用优先队列(堆)或者快速选择算法可以高效地找到数组中最小的k个元素。堆可以在O(n log k)时间内完成,而快速选择的平均时间复杂度为O(n)。 6. **统计数字出现频率** 这是一个计数问题...

    查找第k小2_K._查找第k小_

    在给定的标题“查找第k小2”中,我们可以推断这是一个关于查找第k小元素的算法问题的第二个版本,可能与之前的实现有所不同或者更进阶。描述提到“完成算法课程作业,随机生成1000个数字,短时间内找到第k小”,这...

    查找第K小的元素2

    2. **优先队列/堆**:使用最小堆来存储前K个元素,每次插入新元素时,如果堆的大小超过K,则将堆顶元素(最大值)移除,这样可以保证堆中始终包含当前的K个最小元素。 3. **线性时间复杂度的解决方案**:例如,可以...

    微软编程面试100题

    5. **查找最小k个元素**: 使用快速选择或堆排序可以解决。快速选择可以在平均情况下达到O(n)的时间复杂度,堆排序则能保证O(n log k)的时间复杂度,用于找出最小的k个元素。 6. **数字分配问题**: 这是一个计数...

    微软等公司数据结构%2B算法面试第1-100题汇总

    5. **查找最小k个元素** 快速选择算法可以解决这个问题,它基于快速排序的分治思想,但不需要完全排序。在每次划分时,选择一个基准元素,将小于基准的元素放到它的左边,大于或等于的元素放到右边。如果k在基准的...

    微软等公司数据结构+算法面试第1-80题汇总

    5. **查找最小k个元素**: 使用优先队列(堆)解决,每次将新元素与堆顶元素比较,如果较小则替换堆顶元素并调整堆。重复此过程,直到找到k个最小元素。 6. **频率分配问题**: 可以用哈希表记录上排每个数出现的...

    算法:求第k小元素

    当弹出的元素个数等于k-1时,堆顶剩下的元素就是第k小的元素。堆排序法的时间复杂度为O(n log n)。 3. **线性时间复杂度的解决方案**: 当数据集支持随机访问时,可以使用“最小堆+跳跃”算法,也称为“三数取中”...

    算法100题(C/C++)

    5. **查找最小k个元素**: - 可以使用快速选择算法,该算法是快速排序的变体,专门用于寻找数组中的第k小元素。在平均情况下,时间复杂度为O(n),最坏情况下为O(n^2)。 6. **腾讯面试题:数组分配问题**: - 这是...

Global site tag (gtag.js) - Google Analytics