luogu-B2093 查找特定的值

GESP三级练习，一维数组练习（C++三级大纲中5号知识点，一维数组），难度★☆☆☆☆。

luogu-B2093 查找特定的值

题目要求

题目描述

在一个序列（下标从 $0$ 开始）中查找一个给定的值，输出第一次出现的位置。

输入格式

第一行包含一个正整数 $n$，表示序列中元素个数。$1 \le n \le 10000$。

第二行包含 $n$ 个整数，依次给出序列的每个元素，相邻两个整数之间用单个空格隔开。元素的绝对值不超过 $10000$。

第三行包含一个整数 $x$，为需要查找的特定值。$x$ 的绝对值不超过 $10000$。

输出格式

若序列中存在 $x$，输出 $x$ 第一次出现的下标； 否则输出 -1。

输入输出样例 #1

输入 #1

5
2 3 6 7 3
3

输出 #1

1

题目分析

解题思路

1. 首先需要输入数组长度 $n$，然后输入 $n$ 个整数存入数组中
2. 再输入需要查找的特定值 $x$
3. 从数组第一个元素开始向后遍历，查找是否存在值为 $x$ 的元素
4. 如果找到值为 $x$ 的元素，则输出其下标位置并结束程序
5. 如果遍历完整个数组都没有找到值为 $x$ 的元素，则输出 $-1$

复杂度分析：

• 输入n个数的时间复杂度为 $O(n)$
• 遍历数组查找特定值的时间复杂度为 $O(n)$
• 因此总时间复杂度为 $O(n)$
• 空间复杂度为 $O(n)$，需要存储n个整数的数组

{% include custom/custom-post-content-inner.html %}

示例代码

#include <iostream>
using namespace std;
int a[10000];
int main() {
    // 定义数组长度变量
    int n;
    // 定义要查找的数
    int x;
    // 输入数组长度
    cin >> n;
    // 循环输入n个数到数组
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // 输入要查找的数
    cin >> x;
    // 遍历数组查找x
    for (int i = 0; i < n; i++) {
        // 找到x则输出下标并结束程序
        if (x == a[i]) {
            cout << i;
            return 0;
        }
    }
    // 未找到则输出-1
    cout << "-1";
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号