零起点学算法85——数组中插入一个数

题目描述：

给定一个有序数组和一个数，将这个数插入到数组中，并保证数组仍然有序。

输入格式：

第一行输入一个整数 n，表示数组的长度。

第二行输入 n 个整数，表示给定的有序数组。

第三行输入一个整数 x，表示要插入的数。

输出格式：

输出 n+1 个整数，表示插入新数后的数组。

输入样例：

5
1 3 4 6 8
5

输出样例：

1 3 4 5 6 8

算法1

(暴力枚举) $O(n)$

直接从头到尾遍历数组，找到第一个大于等于插入数的位置，然后将插入数插入到该位置。

时间复杂度

遍历一次数组，时间复杂度为 $O(n)$。

C++ 代码

算法2

(二分查找) $O(logn)$

由于数组是有序的，可以使用二分查找找到第一个大于等于插入数的位置，然后将插入数插入到该位置。

时间复杂度

二分查找的时间复杂度为 $O(logn)$。

C++ 代码

相关问题

零起点学算法101——统计字母数字等个数

这道题的思路比较简单，我们只需要遍历字符串，然后统计其中字母、数字、空格和其他字符的个数即可。

具体实现可以使用一个计数器数组，分别记录字母、数字、空格和其他字符的个数。然后遍历字符串，对于每个字符，判断它属于哪一类，然后将对应的计数器加一即可。

最后输出各个计数器的值即可得到结果。

零基础学C/C++94——数组中查找数

在这个问题中，用户提供了两段代码，分别是引用\[1\]和引用\[2\]。这两段代码都是用来在一个数组中查找指定数的位置。

引用\[1\]是一个C++代码示例，它使用了iostream和stdio.h头文件，并使用了命名空间std。代码中使用了一个while循环来不断读取输入的n值，然后创建一个大小为n的整型数组a，并通过for循环读取数组的元素。接下来，代码读取了一个整数m，并使用for循环遍历数组a，查找是否有与m相等的元素。如果找到了相等的元素，则将其位置赋值给变量t，并跳出循环。最后，根据t的值输出结果。

引用\[2\]是另一个C代码示例，它使用了stdio.h头文件。代码中同样使用了一个while循环来不断读取输入的n值，然后创建一个大小为n的整型数组a，并通过for循环读取数组的元素。接下来，代码读取了一个整数m，并使用for循环遍历数组a，查找是否有与m相等的元素。如果找到了相等的元素，则将其位置赋值给变量count，并将flag设置为1，表示找到了。最后，根据flag的值输出结果。

综上所述，这两段代码都是用来在一个数组中查找指定数的位置。它们的实现方式略有不同，但都能达到相同的目的。
#### 引用[.reference_title]
- *1* [1143: 零起点学算法50——数组中查找数](https://blog.csdn.net/weixin_43965597/article/details/113104995)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* [问题 C: 零起点学算法82——数组中查找数](https://blog.csdn.net/chenhannan0024/article/details/127568844)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]