给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：
，数组中每个数的大小
要求：空间复杂度 )
，时间复杂度 )
[编程题]最小的K个数
没耐心了。大堆还要自己搭，此题考虑过我们C的吗？就知道想着C+。三行给你搞定，跑的还很快。
int cmp(const void *a, const void *b) {
return *(int*)a > *(int*)b? 1: -1;
}
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
qsort(input, inputLen, sizeof(int), cmp);
*returnSize = k;
return input;
}
编辑于 2024-03-20 11:04:57
回复(0)
int result[10000];
/* 找出最小值并且把这个值移出数组*/
int GetMinNum(int* input, int inputlen){
int tmp = input[0];
int index = 0;
for (int m = 1; m < inputlen; m++){
if (tmp > input[m]){
tmp = input[m];
index = m;
}
}
for (int n = index; n < inputlen-1; n++)
{
input[n] = input[n+1];
}
return tmp;
}
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
// write code here
for (int i = 0; i < k; i++){
result[i] = GetMinNum(input,inputLen);
inputLen--;
}
*returnSize = k;
return result;
}
编辑于 2024-03-14 16:15:21
回复(0)
基数排序
其实一开始的思路是自上而下来筛选的
比方说我存数的数组前x个(最高位为0，1，2..)的个数和大于k时终止，这样可以筛掉一些数
但是还是很慢
#include <stdbool.h>
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
if(k == 0){
return NULL;
}
int **tmp1 = malloc(sizeof(int*) * 10);
//数组长度标志
int flag[10] = {0};
int i;
for(i = 0 ;i<10;i++){
tmp1[i] = malloc(sizeof(int) * inputLen);
}
int max = 0;
for(i = 0;i<inputLen ;i++){
if(input[i] > max){
max = input[i];
}
}
//基数排序思路
//计算位数
int ctn = 10;
while(max/ctn!=0){
ctn = ctn * 10;
}ctn = ctn/10;
int ctn2 = 1;
while(ctn2<=ctn){
//从低位到高位存储数字
for(i = 0;i<inputLen;i++){
int index = input[i]/ctn2 % 10;
tmp1[index][flag[index]] = input[i];
flag[index]++;
}i = 0;
inputLen = 0;
int j = 0;
while(j<10){
if(i >=flag[j]){
j++;
i = 0;
continue;
}
input[inputLen++] = tmp1[j][i++];
}i = 0;j = 0;
//重置数组长度;
while(i<10){
flag[i] = 0;
i++;
}i = 0;
ctn2 = ctn2*10;
}
*returnSize = k;
return input;
}
发表于 2023-10-13 17:21:42
回复(0)
int portion(int *arr, int low, int hight)
{
if(low+1>=hight)
{
return -1;
}
int temp = arr[low];
while (low < hight) {
while (low < hight && temp <= arr[hight]) {
hight--;
}
arr[low] = arr[hight];
while (low < hight && temp >= arr[low]) {
low++;
}
arr[hight] = arr[low];
}
arr[low] = temp;
return low;
}
void quick_sort(int *arr, int low, int hight)
{
if(low+1>=hight)
{
return;
}
int mid = portion(arr, low, hight);
quick_sort(arr, mid+1, hight);
quick_sort(arr, low, mid-1);
}
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
// write code here
if (k == 0) {
return NULL;
}
quick_sort(input, 0, inputLen - 1);
int i = k;
int * arr = (int*)malloc(sizeof(int)*k);
for (i = 0; i < k; i++) {
arr[i] = input[i];
}
*returnSize = i;
return arr;
}
发表于 2023-09-14 14:06:00
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param inputLen int input数组长度
* @param k int整型
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
int QuickSort(int*arr,int left,int right)
{
if(left+1>=right)
{
return -1;
}
int temp=arr[left];
while(left<right)
{
while(left<right&&arr[right]>=temp)
{
--right;
}
arr[left]=arr[right];
while(left<right&&arr[left]<=temp)
{
++left;
}
arr[right]=arr[left];
}
arr[left]=temp;
return left;
}
void Merge(int*arr,int left,int right)
{
if(left+1>=right)
{
return;
}
int pos=QuickSort(arr,left,right);
Merge(arr,left,pos-1);
Merge(arr,pos+1,right);
}
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize )
{
// write code here
Merge(input,0,inputLen-1);
int *arr=(int*)malloc(sizeof(int)*k);
if(NULL==arr)
{
return NULL;
}
int i=0;
for(i=0;i<k;++i)
{
arr[i]=input[i];
}
*returnSize=k;
return arr;
}
发表于 2023-08-02 21:14:12
回复(0)
int privot(int a[], int low, int high);
void quicksort(int a[], int low, int high);
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
// write code here
int i;
int *traget = (int *)malloc(sizeof(int)*k); //创造返回的数组
if (k == 0) return NULL;
quicksort(input, 0, inputLen-1);
for (i = 0; i < k; i++){ //赋值最小的k个
traget[i] = input[i];
}
*returnSize = i;
return traget;
}
int privot(int a[], int low, int high){ //划分
int p = a[low];
while (low < high){
while(low < high && a[high] >= p) high--;
a[low] = a[high];
while(low < high && a[low] <= p) low++;
a[high] = a[low];
}
a[low] = p;
return low;
}
void quicksort(int a[], int low, int high){ //快排
if (low < high) {
int pri = privot(a, low, high);
quicksort(a, low, pri-1);
quicksort(a, pri+1, high);
}
}
发表于 2023-03-17 15:49:38
回复(0)
void heapAdjust(int* arr,int i,int n){
int rc=arr[i];//将以序号为i的结点为根结点的子树建成堆
for(int j=i*2+1;j<n;j=j*2+1){//i是双亲结点，j是孩子结点
if(j<n-1 && arr[j]<arr[j+1])//j如果不是最后一个结点，则有右孩子
j++;//右孩子较大
if(rc>=arr[j])//建立大根堆
break;
arr[i]=arr[j];
i=j;
}
arr[i]=rc;
}
void createHeap(int* arr,int n){
for(int i=n/2-1;i>=0;i--)
heapAdjust(arr,i,n);
}
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
*returnSize=0;
if(inputLen==0)
return NULL;
*returnSize=k;
createHeap(input,k);//数组前k个元素初建大根堆
int i;
for(i=k;i<inputLen;i++){//从数组下标k开始，依次和前面已经建好的堆顶元素相比较
if(input[i]<input[0]){
int tmp=input[0];
input[0]=input[i];
input[i]=tmp;
heapAdjust(input,0,k);//重新调整
}
}
int* res=(int *)malloc(sizeof(int)*k);
for(i=0;i<k;i++)
res[i]=input[i];
return res;
}
发表于 2023-03-12 22:03:38
回复(0)
int findmaxnum(int* input, int inputLen) {
int max = 0;;
for(int i = 1; i < inputLen; i++) {
max = (input[i] > input[max] ? i : max);
}
return max;
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param inputLen int input数组长度
* @param k int整型
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
// write code here
*returnSize = k;
for(int i = k; i < inputLen; i++) {
int max = findmaxnum(input, k);
if(input[i] < input[max]) {
int temp = input[i];
input[i] = input[max];
input[max] = temp;
}
}
for(int i = 0; i < k; i++)
{
for(int j = 0; j < k - i - 1; j++)
{
if(input[j] > input[j+1])
{
int temp = input[j];
input[j] = input[j+1];
input[j+1] = temp;
}
}
}
return input;
}
发表于 2023-01-11 16:24:27
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param inputLen int input数组长度
* @param k int整型
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
int comp(const void*a,const void*b)
{
return *(int*)a-*(int*)b;
}
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
// write code here
*returnSize=k;
qsort(input, inputLen,sizeof(int), comp);
return input;
}
发表于 2022-12-25 10:41:27
回复(0)
/**
------------------已验证可以通过--------------------------
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param inputLen int input数组长度
* @param k int整型
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
typedef struct alog
{
int(*find_min)( int*, int);
int*(*min_array)(struct alog, int*,int, int);
}alog_find_minarray;
static int find_min( int* inbuf, int len)
{
int cnt;
int minval = 1000;
int minid = 0;
for(cnt=0;cnt<len;cnt++){
if(minval>inbuf[cnt]){
minval = inbuf[cnt];
minid = cnt;
}
}
inbuf[minid] = 1000;//消除此项
return minval;
}
static int* min_array(struct alog my_alog, int* inbuf, int len, int num)
{
int cnt;
int* outbuf = malloc(num*sizeof(int));//存放在堆里，函数结束，空间不会自动被释放
for(cnt = 0;cnt<num;cnt++){
outbuf[cnt] = my_alog.find_min(inbuf,len);
}
return outbuf;
}
alog_find_minarray my_alog = {
.find_min = find_min,
.min_array = min_array,
};
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
// write code here
*returnSize = k;
return my_alog.min_array(my_alog,input,inputLen,k);
}
发表于 2022-07-25 15:57:24
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param inputLen int input数组长度
* @param k int整型
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#include <stdlib.h>
int cmp(const void *a, const void *b){
return *(int *)a-*(int *)b;
}
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
// write code here
if(k==0 ||input==NULL)return NULL;
if(k>inputLen)return input;
qsort(input,inputLen,sizeof(input[0]),cmp);
input[k] = '\0';
*returnSize = k;
return input;
}
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param inputLen int input数组长度
* @param k int整型
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
#include <stdlib.h>
int cmp(const void *a, const void *b){
return *(int *)a-*(int *)b;
}
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
// write code here
if(k==0 ||input==NULL)return NULL;
if(k>inputLen)return input;
qsort(input,inputLen,sizeof(input[0]),cmp);
input[k] = '\0';
*returnSize = k;
return input;
}
发表于 2022-07-17 16:05:53
回复(0)
我是小白
我的思路大概就是第一次找出数组中最小的一个，把它和输入数组的第一个数交换位置，第二次找从第一次结果的第二个数开始，找最小的数，把它和第一次交换后数组的第二个数交换位置，以此类推。这样n次过后，数组的前n个数就是所求结果啦。
然后我就不知道怎么创建动态数组，cv大法了一个malloc方法，TOT。
问：1.为啥要使*returnSize=k才会有正确输出啊，我这函数中也没有用到returnSize啊？
2.为啥每次编译的大小都不一样，一会儿512k，一会儿416k？
发表于 2021-12-28 16:54:09
回复(0)
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
// write code here
//冒泡排序 5ms 412kb
int i=0,j=0,c=0;
*returnSize=k;
for(j=0;j<inputLen-1;j++){
for(i=0;i<inputLen-1-j;i++){// 之前写成for(i=0;i<inputLen-1;i++)
if(input[i]>input[i+1]){c=input[i+1];input[i+1]=input[i];input[i]=c;}
}
}
return input;
//4ms 432kb
//int i=0,j=0,c=0;
//int*a=(int*)malloc(sizeof(int)*k);
//for(i=0;i<k;i++){a[i]=input[i];}
//*returnSize=k;
//for(i=k;i<inputLen;i++){
//for(j=0;j<k;j++){
//if(input[i]<a[j]){c=input[i];input[i]=a[j];a[j]=c;}
//}
//}
//return a;
}
// write code here
//冒泡排序 5ms 412kb
int i=0,j=0,c=0;
*returnSize=k;
for(j=0;j<inputLen-1;j++){
for(i=0;i<inputLen-1-j;i++){// 之前写成for(i=0;i<inputLen-1;i++)
if(input[i]>input[i+1]){c=input[i+1];input[i+1]=input[i];input[i]=c;}
}
}
return input;
//4ms 432kb
//int i=0,j=0,c=0;
//int*a=(int*)malloc(sizeof(int)*k);
//for(i=0;i<k;i++){a[i]=input[i];}
//*returnSize=k;
//for(i=k;i<inputLen;i++){
//for(j=0;j<k;j++){
//if(input[i]<a[j]){c=input[i];input[i]=a[j];a[j]=c;}
//}
//}
//return a;
}
发表于 2021-11-16 23:30:51
回复(0)
问题信息
难度：
13条回答
3270收藏
189163浏览
通过挑战的用户
查看代码-
2023-03-13 15:46:59
-
2023-03-09 09:29:58
-
2023-02-26 11:56:24 -
2023-02-25 17:15:38 -
2023-02-23 17:07:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
