当前位置：首页 > article >正文

牛客网刷题 | BC122 有序序列判断

article 2024/12/5 3:40:46

目前主要分为三个专栏，后续还会添加：

专栏如下： C语言刷题解析 C语言系列文章我的成长经历

感谢阅读！

初来乍到，如有错误请指出，感谢！

描述

输入一个整数序列，判断是否是有序序列，有序，指序列中的整数从小到大排序或者从大到小排序(相同元素也视为有序)。

数据范围： 3≤n≤50 3≤n≤50 序列中的值都满足 1≤val≤100 1≤val≤100

输入描述：

第一行输入一个整数N(3≤N≤50)。

第二行输入N个整数，用空格分隔N个整数。

输出描述：

输出为一行，如果序列有序输出sorted，否则输出unsorted。

解题步骤

读取输入
- 首先读取一个整数N，表示序列中元素的数量。
- 然后读取接下来的N个整数，并存储在一个数组中。
验证输入有效性
- 检查N是否在有效范围内（3到50）。
- 检查每个输入的整数是否在有效范围内（1到100）。
- 如果输入无效，输出错误信息并退出程序。
判断序列有序性
- 初始化两个计数器cnt1和cnt2为0。cnt1用于记录满足升序条件的相邻元素对数量，cnt2用于记录满足降序条件的相邻元素对数量。
- 遍历数组，比较每一对相邻元素：
  - 如果前一个元素小于等于后一个元素，则cnt1加1。
  - 如果前一个元素大于等于后一个元素，则cnt2加1。
得出结论
- 如果cnt1等于N-1，说明所有相邻元素都满足升序条件，序列是有序的。
- 如果cnt2等于N-1，说明所有相邻元素都满足降序条件，序列是有序的。
- 如果两者都不满足，则序列是无序的。
输出结果
- 根据上述判断结果输出相应的字符串："sorted"或"unsorted"。

#include <stdio.h>

int main() {
    int n, i;
    int arr[50];  // 定义一个大小为50的数组来存储输入的整数
    int cnt1 = 0, cnt2 = 0;  // 分别作为对大小关系的计数

    // 读取第一个整数n，表示序列中元素的数量
    scanf("%d", &n);

    // 检查n是否在有效范围内（3到50）
    if (n < 3 || n > 50) {
        printf("Invalid input\n");
        return 1;
    }

    // 读取接下来的n个整数，并存储在数组arr中
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);

        // 检查每个整数是否在有效范围内（1到100）
        if (arr[i] < 1 || arr[i] > 100) {
            printf("Invalid input\n");
            return 1;
        }
    }

    // 在循环中比较前后两个数的大小关系
    for (i = 0; i < (n - 1); i++) {
        if (arr[i] <= arr[i + 1]) {
            cnt1++;  // 前数小于等于后数，cnt1+1
        } else if (arr[i] >= arr[i + 1]) {
            cnt2++;  // 前数大于等于后数，cnt2+1
        }
    }

    // 若为有序数列，cnt1=n-1，或者cnt2=n-1
    if (cnt1 == n - 1 || cnt2 == n - 1) {
        printf("sorted\n");
    } else {
        printf("unsorted\n");
    }

    return 0;
}

代码解释

读取输入:
- 使用scanf("%d", &n);读取第一个整数n，表示序列中元素的数量。
- 使用循环读取接下来的n个整数，并存储在数组arr中。
验证输入有效性:
- 检查n是否在有效范围内（3到50），如果不在范围内则输出错误信息并退出程序。
- 检查每个整数是否在有效范围内（1到100），如果不在范围内则输出错误信息并退出程序。
判断序列有序性:
- 初始化两个计数器cnt1和cnt2为0。
- 使用循环遍历数组，比较每一对相邻元素的关系，更新cnt1和cnt2。
得出结论:
- 根据cnt1和cnt2的值判断序列是否有序，并输出相应的结果："sorted"或"unsorted"。

关键知识点总结

1. 输入输出操作

scanf: 用于从标准输入读取数据。
- 格式说明符：
  - %d: 整数
  - %f: 浮点数
  - %c: 字符
  - %s: 字符串
printf: 用于向标准输出打印数据。
- 格式说明符：
  - %d: 整数
  - %f: 浮点数
  - %c: 字符
  - %s: 字符串
  - \n: 换行符

2. 数组的使用

定义数组: 定义一个固定大小的数组来存储数据。

int arr[50];  // 定义一个大小为50的整数数组

初始化数组: 可以在定义时初始化数组。

int arr[5] = {1, 2, 3, 4, 5};  // 初始化数组元素

访问数组元素: 通过索引访问和修改数组中的元素。

arr[0] = 10;  // 修改第一个元素
printf("%d\n", arr[1]);  // 访问第二个元素并打印

3. 循环控制结构

for循环: 用于遍历数组或其他重复操作。

for (int i = 0; i < n; i++) {
    // 循环体
}

while循环: 用于在条件为真时重复执行代码块。

int i = 0;
while (i < n) {
    // 循环体
    i++;
}

do-while循环: 至少执行一次循环体，然后根据条件决定是否继续。

int i = 0;
do {
    // 循环体
    i++;
} while (i < n);

4. 条件判断

if语句: 单个条件判断。

if (condition) {
    // 如果条件为真，执行这里的代码
}

if-else语句: 多个条件判断。

if (condition1) {
    // 如果 condition1 为真，执行这里的代码
} else if (condition2) {
    // 如果 condition2 为真，执行这里的代码
} else {
    // 如果所有条件都为假，执行这里的代码
}

switch语句: 多个离散值的条件判断。

switch (expression) {
    case value1:
        // 如果 expression 等于 value1，执行这里的代码
        break;
    case value2:
        // 如果 expression 等于 value2，执行这里的代码
        break;
    default:
        // 如果 expression 不等于任何case，执行这里的代码
}

5. 布尔逻辑

布尔变量: 在C语言中没有内置的布尔类型，但可以用整数0和1来表示布尔值。

int is_true = 1;  // 1 表示 true
int is_false = 0; // 0 表示 false

逻辑运算符:
- &&: 逻辑与
- ||: 逻辑或
- !: 逻辑非

6. 边界条件处理

输入有效性检查: 确保输入的数据在规定范围内。

if (n < 3 || n > 50) {
    printf("Invalid input\n");
    return 1;
}

数组边界检查: 确保数组索引在有效范围内。

for (int i = 0; i < n; i++) {
    // 确保 i 在 [0, n-1] 范围内
}

7. 时间复杂度分析

线性时间复杂度: O(N)，适合题目中N的最大值为50的情况。

for (int i = 0; i < n; i++) {
    // 每次循环执行常数时间的操作
}

其他常见时间复杂度:
- O(1): 常数时间
- O(log N): 对数时间
- O(N^2): 平方时间

8. 代码可读性和健壮性

添加注释: 提高代码的可读性。

// 这是一个注释，解释下面的代码的作用
int result = a + b;

输入验证: 增强代码的健壮性。

if (arr[i] < 1 || arr[i] > 100) {
    printf("Invalid input\n");
    return 1;
}

良好的命名习惯: 使用有意义的变量名。

int numberOfElements;  // 明确表示这是元素的数量

实例演示