我们得到一个包含正数和负数的整数类型数组，比方说，任意给定大小的 arr[] 。任务是重新排列一个数组，使所有正数和负数都应该位于交替的位置，并且如果有额外的正数或负数元素，然后它们将被放置在数组的末尾。
让我们看看这种情况的各种输入输出场景 –
输入 − int arr[] = {4, 2, -1, -1, 6, -3}
输出− 在 O(n) 时间和 O(1) 时间内重新排列正数和负数额外的空间是： 2 – 1 6 -1 4 -3
解释− 我们得到一个大小为 6 的整数数组，其中包含正数和负数元素。现在，我们将重新排列数组，使所有正元素和负数元素位于备用位置，所有额外元素将添加到数组末尾，即 2 -1 6 -1 4 -3 将是最终结果
输入
立即学习“C++免费学习笔记（深入）”；
输入
立即学习“C++免费学习笔记（深入）”；
strong>− int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}
输出 strong>− 在 O(n) 时间和 O(1) 额外空间内对正数和负数重新排列为： 2 – 2 3 -5 5 -3 5 -1 1 3 1 1
解释 – 我们得到一个大小为 12 的整数数组，其中包含正数和负数元素。现在，我们将重新排列数组，使所有正元素和负元素都位于交替位置，并且所有额外元素将添加到数组的末尾，即 2 -2 3 -5 5 -3 5 -1 1 3 1 1 为最终结果
下面程序中使用的方法如下
输入一个整数数组输入元素并计算数组的大小。
在使用 FOR 循环执行重新排列操作之前打印数组。
通过传递数组和数组大小作为参数来调用函数 Rearrangement(arr, size)。
函数 Rearrangement(arr, size) 内部
声明临时整型变量，即temp为-1，正数为temp + 1，负数为0。
开始从 i 到 0 循环，直到 i 小于数组的大小。在循环内部，检查 IF arr[i] 小于 0，然后将 temp 加 1 并调用 C++ STL 的内置方法，即 swap(arr[temp], arr[i]) 并传递 arr[temp] 和 arr[i ] 作为参数。
开始循环，WHILE 正数小于数组大小 AND 负数小于正数 AND arr[负数] 小于 0。在循环内，调用通过传递 arr[负数] 和 arr[正数] 作为参数进行交换。将正数加 1，将负数设置为负数 + 2。
打印结果。
示例
#include using namespace std;void Rearrangement(int arr[], int size){ int temp = -1; for(int i = 0; i 输出
如果我们运行上面的代码，它将生成以下输出
Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3
登录后复制
以上就是在C++中，以O(n)的时间复杂度和O(1)的额外空间重新排列正负数的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2586218.html
