题解 | #小红喜欢1#

题目链接

小红喜欢1

题目描述

给定一个长度为 $n$ 的数组 $a$ ，其中恰好有且仅有一个元素为 $1$ ，其余元素均为 $0$ 。请输出唯一的下标 $i$ （ $1 \le i \le n$ ），满足 $a_i = 1$ 。

解题思路

题目要求我们找到数组中值为 $1$ 的元素的 $1$ -based 下标。由于题目保证有且仅有一个 $1$ ，最直接的方法就是从头到尾遍历数组。

我们可以设置一个从 $1$ 开始的计数器来追踪当前元素的下标。在遍历过程中，检查每一个元素的值。当找到值为 $1$ 的元素时，其对应的计数器的值就是我们所求的下标，此时输出该值并可以结束程序。

代码

c++
java
python

#include <iostream>

using namespace std;

int main() {
    int val;
    int index = 1;
    // 循环读取输入流中的每个整数
    while (cin >> val) {
        // 如果当前数字是1
        if (val == 1) {
            // 输出其对应的1-based下标
            cout << index << '\n';
            // 找到后即可退出循环
            break;
        }
        // 下标加1，继续检查下一个数
        index++;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int index = 1;
        // 循环读取输入流中的每个整数
        while (sc.hasNextInt()) {
            int val = sc.nextInt();
            // 如果当前数字是1
            if (val == 1) {
                // 输出其对应的1-based下标
                System.out.println(index);
                // 找到后即可退出循环
                break;
            }
            // 下标加1，继续检查下一个数
            index++;
        }
    }
}

# 读取一行输入，并按空格分割成字符串列表
nums_str = input().split()
# 将字符串列表转换为整数列表
nums = [int(x) for x in nums_str]
# 使用 list.index() 方法找到值为1的元素的0-based索引，
# 然后加1得到1-based的下标并输出
print(nums.index(1) + 1)

算法及复杂度

算法：线性查找。
时间复杂度：我们需要遍历数组来找到元素 $1$ 。在最坏的情况下（ $1$ 在数组末尾），需要遍历全部 $n$ 个元素。因此，时间复杂度为 $O(n)$ ，其中 $n$ 是数组的长度。
空间复杂度：
- C++ 和 Java 的解法逐个读取和处理数字，没有将整个数组存储在内存中，仅使用了常数个变量。因此，空间复杂度为 $O(1)$ 。
- Python 的解法将所有输入的数字读入一个列表中，该列表需要存储 $n$ 个元素。因此，空间复杂度为 $O(n)$ 。