201612-1 中间数 ccf-白红宇

201612-1 中间数 ccf

阅读量：255 次

发布时间：2019-03-01

本文共 1305 字，大约阅读时间需要 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实现获取本机ip及mac地址(附完整源码)