201612-1 中间数 ccf-白红宇

201612-1 中间数 ccf

阅读量：255 次

发布时间：2019-03-01

本文共 1336 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要找到给定整数序列中的中间数。中间数的定义是：在序列中存在比它小的数的个数等于比它大的数的个数。如果有多个这样的数，它们的值都相同，那么这个值就是中间数。否则，返回-1。

方法思路

排序数组：首先对整数序列进行排序，这样可以方便地计算每个数左右的位置情况。

统计中间数：遍历排序后的数组，对于每个数，计算比它小的数的个数和比它大的数的个数。如果两者相等，则该数是中间数。

记录满足条件的数：使用字典记录满足条件的数及其出现次数。

检查唯一性：最后检查字典，如果只有一个数满足条件，则返回该数；否则返回-1。

解决代码

#include 
   
    
#include 
    
     
#include 
     
using namespace std;
int main() {
    int n;
    vector
      
        v;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    map
       
         candidates;
    for (int x : v) {
        auto it_left = lower_bound(v.begin(), v.end(), x);
        auto it_right = upper_bound(v.begin(), v.end(), x);
        int left = it_left - v.begin();
        int right = v.size() - it_right;
        if (left == right) {
            candidates[x]++;
        }
    }
    if (candidates.empty()) {
        cout << -1;
    } else {
        if (candidates.size() == 1) {
            cout << *(candidates.begin()->first);
        } else {
            cout << -1;
        }
    }
    return 0;
}

代码解释

读取输入：首先读取整数n和数组v。

排序数组：对数组v进行排序。

遍历数组：对于数组中的每个数x，使用lower_bound和upper_bound函数计算比x小的数的个数和比x大的数的个数。

记录中间数：如果左边数目等于右边数目，说明x是中间数，将其记录在字典中。

检查结果：最后检查字典，如果只有一个数满足条件，输出该数；否则输出-1。

这种方法确保了我们正确地找到序列中的中间数，并且处理了所有可能的边界情况。

转载地址：http://mkbx.baihongyu.com/

你可能感兴趣的文章

Objective-C实现miller rabin米勒-拉宾素性检验算法(附完整源码)