用分治法寻找第k小的值(C语言实现)

news/2024/10/18 18:17:18/

经典方法:

#include<stdio.h>
#include<stdlib.h>
int min(int* A, int start, int end)
{if (start == end)return A[start];else{int min1, min2, mid;mid = (start + end) / 2;min1 = min(A,start, mid);min2 = min(A,mid + 1, end);if (min1 < min2)return min1;elsereturn min2;}
}
void Lv(int* b, int* a, int min, int num)
{for (int i = 0,k = 0; k < num;i++){if (a[i] != min){b[k++] = a[i];}}
}
int main()
{int n,min0=0,max0;int a[100], b[100];scanf("%d", &n);int m;scanf("%d", &m);/*int* a = (int*)malloc(m * sizeof(int));*///a[m]int target;scanf("%d", &target);while (n--){for (int i = 0; i < m; i++){scanf("%d", &a[i]);}int j=m,n;                      //此处定义为了不让m受到影响 for (int i = 1,n=j; i <= target; i++){min0 = min(a, 0, --n);  //定义n的意义是如果也用--j会使下面的Lv函数受到影响(看了三遍才找出的错误) Lv(a, a, min0, --j);    //定义j的原因是直接--m会使m的值发生改变,影响第二遍遍历(看了两遍找出的错误) }/*max0 = max(a, 0, m - 1);*/printf("%d\n",min0);}/*free(a);*/return 0;
}


http://www.ppmy.cn/news/714119.html

相关文章

C语言学习笔记: i < j < k 的操作

表达式i < j < k在C语言中是合法的&#xff0c;但是它不是你所期望的意思。因为&#xff1c;运算符是左结合的&#xff0c; 所以这个表达式等价于(i < j) < k. 换句话说&#xff0c; 表达式首先检测l.是否小千j, 然后用比较后产生的结果1或0来和K进行比较。 表达式…

K倍区间(蓝桥杯2017年第八届省赛B组第十题)(C/C++)

题目描述 给定一个长度为 N 的数列&#xff0c;A1, A2,...AN​&#xff0c;如果其中一段连续的子序列 Ai,Ai1⋯Aj​ ( i ≤j ) 之和是 K 的倍数&#xff0c;我们就称这个区间 [i, j]是 K 倍区间。 你能求出数列中总共有多少个 K倍区间吗&#xff1f; 输入描述 第一行包含两…

c语言之求n以内最大的k个素数以及它们的和

描述 编写程序&#xff0c;计算并输出不超过n的最大的k个素数以及它们的和。 输入 在一行中给出n(10≤n≤10000)和k(1≤k≤10)的值。 输出 在一行中按下列格式输出: 素数1素数2…素数k总和值 其中素数按递减顺序输出。若n以内不够k个素数&#xff0c;则按实际个数输出。 输…

查找第K小元素(C语言版)

今天在看《算法&#xff1a;C语言实现》时&#xff0c;在快速排序那一章最后一节讲述了利用快速排序的思想&#xff0c;快速排序每次划分后在枢轴的左边的元素都比枢轴小(或相等)&#xff0c;在枢轴右边的数都比枢轴大(或相等)&#xff0c;而划分后枢轴本身就放在了(有序时)它自…

【已解决】C语言从n个不同的元素中,每次取出k个不同的元素

本博文源于c语言基础&#xff0c;旨在通过对思路的解释&#xff0c;编写出组合数的代码&#xff0c;博文分为以下模块1、问题再现&#xff0c;2、代码测试效果3、核心解题思路4、完整源码 重点看解题思路 1、问题再现 从n个不同的元素中&#xff0c;每次取出k个不同的元素&am…

C语言学习之求∑k(k=100)+∑K*k(k=50)+∑1/k(k=10)

求∑k(k100)∑K*k(k50)∑1/k(k10) #include <stdio.h> #include <math.h> void main(){double as0,bs0,cs0;for(int i1;i<100;i){asi;}printf("1...100%d\n",as);for(int j1;j<50;j){bspow(j,2);}printf("1*1...50*50%d\n",bs);for(int …

C语言 计算∑(k=1—100)k+∑(k=1—50)k²+∑(k=1—10)1/k的值

#include <stdio.h> int main(){int n1100,n250,n310;double k,s10,s20,s30;for(k1;k<n1;k){ //计算1—100的和s1s1k;}for(k1;k<n2;k){ //计算1—50的和s2s2k*k;}for(k1;k<n3;k){ //计算1-10的各倒数和s3s31/k;}printf("sum%6f",s1s2s3);return 0; }

c语言三种方法求n的k次方

// 方法一&#xff1a;递归 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int Power(int n,int k) //题目中有两个变量&#xff0c;在设计函数时需要两个形参 {if (k 0){return 1;}else if(k1) {return n;}else{return n*Power(…