ccf-中间数-Java实现

ゝ一纸荒年。 2022-05-30 11:23 188阅读 0赞

先贴上结果： ![70][]

问题描述

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

输入格式

输入的第一行包含了一个整数 n，表示整数序列中数的个数。  
　　第二行包含 n个正整数，依次表示 a 1,  a 2, …,  an。

输出格式

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

样例输入

6  
2 6 5 6 3 5

样例输出

样例说明

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

样例输入

4  
3 4 6 7

样例输出

\-1

样例说明

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

样例输入

5  
3 4 6 6 7

样例输出

\-1

样例说明

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

思路：

先找到最中间的数字，然后往左往右遍历，分别找到第一个不等于中间数的数字下标，然后计算两边的数字个数，如果相同则

说明存在中间数，否则不存在

import java.util.*;
    
    public class Main {
    
        public static void main(String args[]) {
    
    
            Scanner scan = new Scanner(System.in);
    
            int n = scan.nextInt();
    
            List<Integer>list=new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(scan.nextInt());
            }
            int result=-1;
            if(n==1){
                result=list.get(0);
            }else if(n==2){
                if(list.get(0)==list.get(1)){
                    result=list.get(0);
                }else{
                    result=-1;
                }
            }
            else {
                Collections.sort(list);
                int mid = 0;
                if (n % 2 == 0) {
                    mid = n / 2 - 1;
                } else {
                    mid = (n - 1) / 2;
                }
                int temp = list.get(mid);
    
                int left = 0;
                int right = 0;
                for (int i = mid - 1; i >= 0; i--) {
                    if (list.get(i) != temp) {
                        left = i;
                        break;
                    }
                }
                for (int i = mid + 1; i < n; i++) {
                    if (list.get(i) != temp) {
                        right = i;
                        break;
                    }
                }
                if (left + 1 == n - right) {
                    result = temp;
                } else {
                    result = -1;
                }
            }
            System.out.println(result);
        }
    
    }

[70]: /images/20220530/662c9ae2545441f592884097c6a2c823.png