首页 > 代码库 > 100w 个整数里取出最大的 500 个, 可以转换为 n 个数里取出最大的 m 个
100w 个整数里取出最大的 500 个, 可以转换为 n 个数里取出最大的 m 个
/** * 100w 个整数里取出最大的 500 个: * 可以转换为 n 个数里取出最大的 m 个,其中 m < n,采用堆排序实现,时间复杂度为 n + nlogm * 举例:12 20 9 18 7 14 几个数中取出最大的三个: * 做法:遍历所需计算的整数。创建一个节点数为3的最小堆,当堆装满后,再来的数与根节点对比,如果比根节点大,替换,然后再走到根节点相应的位置,图例如下: * (0) (1) (2) (3) (4) (5) (6) (7) (8) * 12 12 12 12 9 18 12 7 丢弃 14 * / / \ / \ / \ / \ / \ / * 20 20 9 9 20 12 20 12 20 18 20 18 20 * 希望读者有更好方法的不吝赐教 */ #include<stdio.h> #define LENGTH(s) (sizeof(s) / sizeof(s[0])) //取数组长度 define 不是定义数组,而是把一段代码取一个别名 /** * 交换两个整数 */ void swap(int *a, int *b){ *a = *a ^ *b; *b = *a ^ *b; *a = *a ^ *b; } /** * 将节点与其子节点对比,如果比子节点大,则与其交换,替换完了再保证被替换的同节点比右边的弟兄节点小,否则左右兄弟节点交换 */ int shift_down(int *r, int i){ if( i >= LENGTH(r) ) return i; int left, right, last_left; left = 2 * i +1; // 如果节点比左了节点大,交换,如注释中第(6)步 if( r[i] > r[left] ){ swap(&r[i], &r[left]); last_left = shift_down(r, left); // 如果右节点存在,左右对比,保证左节点比右节点小,如注释中第(3)步 if( last_left <= sizeof(r) - 2 ){ if(r[last_left] > r[last_left+1]) swap(&r[last_left], &r[last_left+1]); } return 0; }else{ return i; } } /** * 判断节点是否为右节点 */ int is_right(int i){ return (i > 0) && ( (i -1) % 2 == 1); } /** * 将节点与父节点对比,如果比爷节点大,则民其交换,替换完再保证左节点始终比右节点小 */ int shift_up(int *r, int i){ if( i <= 0 ) return i; int parent; parent = (i -1) / 2; if(r[parent] > r[i]){ swap(&r[parent], &r[i]); shift_up(r, parent); } return 0; } int main(){ int r_size = 3; // 取出结果数 int arr[8] = {12, 20, 9, 18, 7, 14, 21, 28}; //待处理数组 int r[r_size]; int arr_size, i = 0, result_size = 0; arr_size = LENGTH(arr); for( i = 0; i < arr_size; i++ ){ //判断结果堆是否满,未满直接加上,若满与第一个对比 if( result_size >= r_size ){ if( arr[i] > r[0] ){ //替换根节点,如注释中第(5)步 r[0] = arr[i]; // 调整位置,将最小位置到根节点,如注释中第(6)步 shift_down(r, 0); } }else{ // 如果根节点还没填满,在节点末插入一个新节点 r[result_size] = arr[i]; // 如果是右节点,与左节点对比,如果比左节点小,左右交换 if( is_right(result_size) && r[result_size] < r[result_size-1] ) swap(&r[result_size], &r[result_size-1]); shift_up(r, result_size); result_size ++; } } for(i = 0; i < r_size; i++){ printf("\n %d: %d", i, r[i]); } return 0; }
100w 个整数里取出最大的 500 个, 可以转换为 n 个数里取出最大的 m 个
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。