牛牛现在有1000个整数,每个数字都在1~200之间,数字随机排布。假设牛牛不允许你使用任何排序方法将这些整数有序化,你能快速找到从0开始的第450小的数字吗?(从小到大第450位)
区块链毕设网qklbishe.com为您提供问题的解答
牛牛现在有1000个整数,每个数字都在1~200之间,数字随机排布。假设牛牛不允许你使用任何排序方法将这些整数有序化,你能快速找到从0开始的第450小的数字吗?(从小到大第450位)
题目不让用排序。。
那就变成了数据结构经典题:找一个序列里第k大的数字,所以答案就是手搓一个小根堆(嵌入式C不让用STL真的很难受)
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param numbers int整型一维数组 * @param numbersLen int numbers数组长度 * @return int整型 * * C语言声明定义全局变量请加上static,防止重复定义 */ int heap[1005]; int p=0; void put(int i){ int t,tmp; if (i==0) return; t=i/2; if (heap[i]<heap[t]){ tmp=heap[i]; heap[i]=heap[t]; heap[t]=tmp; put(t); } } void get(int i){ int t,tmp; if (2*i>p) return; t=2*i; if (t+1<=1000 && heap[t]>heap[t+1]) t++; if (heap[t]<heap[i]){ tmp=heap[i]; heap[i]=heap[t]; heap[t]=tmp; get(t); } } int find(int* numbers, int numbersLen ) { // write code here int i; for (i=0; i<1000; i++){ p++; heap[p]=numbers[i]; put(p); } for (i=1; i<=450; i++){ heap[1]=heap[p]; p--; get(1); } return heap[1]; }
59:18
以上就是关于问题牛牛现在有1000个整数,每个数字都在1~200之间,数字随机排布。假设牛牛不允许你使用任何排序方法将这些整数有序化,你能快速找到从0开始的第450小的数字吗?(从小到大第450位)的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码,定制。
区块链NFT链游项目方科学家脚本开发培训