首页 > 代码库 > 15、中间数
15、中间数
问题描述
在一个整数序列a1, a2, …, an中,如果存在某个数,大于它的整数数量等于小于它的整数数量,则称其为中间数。在一个序列中,可能存在多个下标不相同的中间数,这些中间数的值是相同的。
给定一个整数序列,请找出这个整数序列的中间数的值。
给定一个整数序列,请找出这个整数序列的中间数的值。
输入格式
输入的第一行包含了一个整数n,表示整数序列中数的个数。
第二行包含n个正整数,依次表示a1, a2, …, an。
第二行包含n个正整数,依次表示a1, a2, …, an。
输出格式
如果约定序列的中间数存在,则输出中间数的值,否则输出-1表示不存在中间数。
样例输入
6
2 6 5 6 3 5
2 6 5 6 3 5
样例输出
5
样例说明
比5小的数有2个,比5大的数也有2个。
样例输入
4
3 4 6 7
3 4 6 7
样例输出
-1
样例说明
在序列中的4个数都不满足中间数的定义。
样例输入
5
3 4 6 6 7
3 4 6 6 7
样例输出
-1
样例说明
在序列中的5个数都不满足中间数的定义。
评测用例规模与约定
对于所有评测用例,1 ≤ n ≤ 1000,1 ≤ ai ≤ 1000。
解题思路:这道题比较简单,寻找是否存在有一个中间数,使得大于它和小于它的数一样多。先将数组进行排序,有利于寻找中间数,我使用的是选择排序。之后按照数组的个数为奇数还是偶数进行分类讨论即可。
具体代码:
1 #include<stdio.h> 2 void sort(int *number, int n){ 3 int i, j, k,temp; 4 for (i = 0; i < n - 1; i++){ 5 k = i; 6 for (j = i + 1; j < n; j++){ 7 if (*(number + j) < *(number + k)) 8 k = j; 9 } 10 temp = *(number + k); 11 *(number + k) = *(number + i); 12 *(number + i) = temp; 13 } 14 } 15 16 int main(){ 17 int n,i,j,num[1000]; 18 scanf("%d", &n); 19 for (i = 0; i < n; i++) 20 scanf("%d", &num[i]); 21 sort(num, n); 22 int low, high,middle,flag; 23 low = high =flag= 0; 24 middle = (n - 1) / 2; 25 if (n % 2 == 1){ 26 for (j = 0; j < middle; j++){ 27 if (num[j] != num[middle]) 28 low++; 29 } 30 for (j = middle + 1; j < n; j++){ 31 if (num[j] != num[middle]) 32 high++; 33 } 34 if (low == high) 35 flag = 1; 36 } 37 else{ 38 if (num[middle] == num[middle + 1]){ 39 for (j = 0; j < middle; j++){ 40 if (num[j] != num[middle]) 41 low++; 42 } 43 for (j = middle + 2; j < n; j++){ 44 if (num[j] != num[middle]) 45 high++; 46 } 47 if (low == high) 48 flag = 1; 49 } 50 } 51 if (flag == 1) 52 printf("%d\n", num[middle]); 53 else 54 printf("-1\n"); 55 return 0; 56 }
做题感悟:这道题应该属于CCF中送分的题目,到时候考试的时候一定拿下。
15、中间数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。