Love丶FFC's Blog

CCF-CSP_20161201:中间数

2019-10-09 15:05:46
阅读:507   •   评论:8
标签:,

问题描述

在一个整数序列a1a2, …, an中,如果存在某个数,大于它的整数数量等于小于它的整数数量,则称其为中间数。在一个序列中,可能存在多个下标不相同的中间数,这些中间数的值是相同的。

给定一个整数序列,请找出这个整数序列的中间数的值。

输入格式

输入的第一行包含了一个整数n,表示整数序列中数的个数。

第二行包含n个正整数,依次表示a1a2, …, an

输出格式

如果约定序列的中间数存在,则输出中间数的值,否则输出-1表示不存在中间数。样例输入

6
2 6 5 6 3 5

样例输出

5

样例说明

比5小的数有2个,比5大的数也有2个。

样例输入

4
3 4 6 7

样例输出

-1

样例说明

在序列中的4个数都不满足中间数的定义。

样例输入

5
3 4 6 6 7

样例输出

-1

样例说明

在序列中的5个数都不满足中间数的定义。

评测用例规模与约定

对于所有评测用例,1 ≤ n ≤ 1000,1 ≤ ai ≤ 1000。

编程语言:Java

解题思想:

1.首先对序列进行排序。

2.判断该序列元素个数为偶数/奇数。

3.偶数如果存在中间数,则至少存在两个中间数,且中间数必然相等,奇数如果存在中间数,则判断中间数与左边右边的情况(若奇数存在多个中间数,用此方法也一样可以进行判断)。

时间复杂度:O(n)

IDE代码如下:

  1. package CCF_CSP;
  2.  
  3. import java.util.Arrays;
  4. import java.util.Scanner;
  5.  
  6. public class _20161201_100point {
  7.  
  8. public static void main(String[] args) {
  9. Scanner scanner = new Scanner(System.in);
  10. int n = scanner.nextInt(); //数字的个数
  11. int[] num = new int[n];
  12.  
  13. for(int i=0;i<n;i++)
  14. {
  15. num[i] = scanner.nextInt();
  16. }
  17.  
  18. Arrays.parallelSort(num); //调用排序api
  19.  
  20. int countleft = 0;
  21. int countright = 0;
  22. if(n%2 == 0) //数字个数为偶数
  23. {
  24. if(num[n/2] == num[n/2-1]) //最中间两数相等才有判断的需要,否则不可能存在中间数
  25. {
  26. for(int i=0;i<n/2;i++) //左边
  27. {
  28. if(num[i]<num[n/2])
  29. {
  30. countleft++;
  31. }
  32. }
  33. for(int i=n/2-1;i<n;i++) //右边
  34. {
  35. if(num[i]>num[n/2])
  36. {
  37. countright++;
  38. }
  39. }
  40. System.out.println(countleft==countright?num[n/2]:-1); //条件表达式
  41. }
  42. else
  43. {
  44. System.out.println(-1);
  45. }
  46. }
  47. else //数字个数为奇数
  48. {
  49. for(int i=0;i<n/2;i++) //左边
  50. {
  51. if(num[i]<num[n/2])
  52. {
  53. countleft++;
  54. }
  55. }
  56. for(int i=n/2+1;i<n;i++) //右边
  57. {
  58. if(num[i]>num[n/2])
  59. {
  60. countright++;
  61. }
  62. }
  63. System.out.println(countleft==countright?num[n/2]:-1); //条件表达式
  64. }
  65. }
  66.  
  67. }
  68.  

评论板

共有 8 条评论

  1. fruinly

    cheapest cialis generic online It has been clearly demonstrated that coxsackieviral 2A Pro can directly cleave dystrophin, that CVB3 infection of the heart is associated with disruption of the dystrophin glycoprotein complex, and that dystrophin deficiency can have a role in determination of susceptibility to enteroviral mediated cardiomyopathy

  2. engarma

    best viagra tablet name for man Louis CvWcHqzSfisPg 5 29 2022

  3. Preliaf

    Administrative Contact Petrov, Vitaly vitalypetrov76 yahoo buying cialis generic Both SLRPs have four keratan sulfate GAG chains

  4. Preliaf

    Ephedra Diet Pills With Vitamins buy cialis online in usa

  5. OjemnIvdT

    Placebo- Controlled study cialis 20mg for sale

--------查看该分类下最新文章--------
^
新版博客正在完善中!域名:http://www.loveffc:8080,点击跳转,完全移植后将去除端口号。

Copyright © 2018 - 2021 FFC的小站 - 滇 ICP 备 18010780 号 - 1

- Powered by WordPress & AliYun · Theme by FFC -

- Environment by Windows & XAMPP · Designed by WebStorm & VSCode -

已运行:

访问量:454572