丢失报文位置 - 华为机试真题题解

题目描述

某通信系统持续向外发送报文，使用数组 nums 保存 n 个最近发送的报文，用于在报文未达到对端的情况下重发。报文使用序号 sn 表示，序号 sn 按报文发送顺序从小到大排序，相邻报文 sn 不完全连续且可能相同。报文使用循环覆盖的方式保存，即 nums 数组填满后，从头开始保存新的报文。假设需要重发序号为 sn 的报文。请找出序号为 sn 的报文在数组中的起始位置和结束位置。

输入

第一行输入：数组 nums 的大小 n，取值范围为 [0, 10000]。
第二行输入：数组中的所有报文序号 sn，sn 取值范围为 [0, 100000]。
第三行输入：需要重发的报文序号 sn，取值范围为 [0, 100000]。

输出

输出两个整数 start 和 end，表示需要重发的报文序号 sn 在数组中的起始和结束下标。

示例1

输入：
7
0 0 1 2 2 5 6
1

输出：
2 2

解释：
nums 数组大小为 7，保存了 7 个报文，sn 分别是 0 0 1 2 2 5 6，sn 为 1 的报文在数组中仅有 1 个，下标是 2，因此输出 2 2。

示例2

输入：
7
0 0 1 2 2 5 6
2

输出：
3 4

解释：
nums 数组大小为 7，保存了 7 个报文，sn 分别是 0 0 1 2 2 5 6，sn 为 2 的报文在数组中有 2 个，下标分别是 3 和 4，因此输出 3 4。

示例3

输入：
7
4 4 7 8 2 3 4
4

输出：
6 1

解释：
nums 数组大小为 7，保存了 7 个报文，sn 分别是 4 4 7 8 2 3 4，sn 为 4 的报文在数组中有 3 个，下标分别是 0、1 和 6。说明 nums 数组存在记录满了从头开始记录的情况，因此输出 6 1。

C++

[代码仅供学习参考并未进行大量数据测试]

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n);

    // 最小报文sn的索引位置
    int min_sn_idx = 0;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        if (nums[i] < nums[min_sn_idx]) min_sn_idx = i;
    }

    int sn;
    cin >> sn;
    // sn的报文在数组中的起始位置和结束位置
    int start = -1, end = -1;
    for (int i = 0; i < n; i++) {
        // 因为题意说 “序号 `sn` 按报文发送顺序从小到大排序”，因此从最小报文开始遍历数组，并同时更新 start 和 end
        int idx = (i + min_sn_idx) % n;
        if (nums[idx] == sn) {
            if (start == -1) start = idx;
            end = idx;
        }
    }

    cout << start << " " << end << endl;

    return 0;
}

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏