搜索
首页后端开发C++在C++中,以O(n)的时间复杂度和O(1)的额外空间重新排列正负数

在C++中,以O(n)的时间复杂度和O(1)的额外空间重新排列正负数

我们得到一个包含正数和负数的整数类型数组,比方说,任意给定大小的 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 将是最终结果

输入

输入

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 <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
   int temp = -1;
   for(int i = 0; i < size; i++){
      if (arr[i] < 0){
         temp++;
         swap(arr[temp], arr[i]);
      }
   }
   int positive = temp + 1;
   int negative = 0;
   while(positive < size && negative < positive && arr[negative] < 0){
      swap(arr[negative], arr[positive]);
      positive++;
      negative = negative + 2;
   }
}
int main(){
   int arr[] = {4, 2, -1, -1, 6, -3};
   int size = sizeof(arr)/sizeof(arr[0]);
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

输出

如果我们运行上面的代码,它将生成以下输出

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)的额外空间重新排列正负数的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:tutorialspoint。如有侵权,请联系admin@php.cn删除
C的未来:改编和创新C的未来:改编和创新Apr 27, 2025 am 12:25 AM

C 的未来将专注于并行计算、安全性、模块化和AI/机器学习领域:1)并行计算将通过协程等特性得到增强;2)安全性将通过更严格的类型检查和内存管理机制提升;3)模块化将简化代码组织和编译;4)AI和机器学习将促使C 适应新需求,如数值计算和GPU编程支持。

C的寿命:检查其当前状态C的寿命:检查其当前状态Apr 26, 2025 am 12:02 AM

C 在现代编程中依然重要,因其高效、灵活和强大的特性。1)C 支持面向对象编程,适用于系统编程、游戏开发和嵌入式系统。2)多态性是C 的亮点,允许通过基类指针或引用调用派生类方法,增强代码的灵活性和可扩展性。

C#vs. C性能:基准测试和注意事项C#vs. C性能:基准测试和注意事项Apr 25, 2025 am 12:25 AM

C#和C 在性能上的差异主要体现在执行速度和资源管理上:1)C 在数值计算和字符串操作上通常表现更好,因为它更接近硬件,没有垃圾回收等额外开销;2)C#在多线程编程上更为简洁,但性能略逊于C ;3)选择哪种语言应根据项目需求和团队技术栈决定。

C:死亡还是简单地发展?C:死亡还是简单地发展?Apr 24, 2025 am 12:13 AM

1)c relevantduetoItsAverity and效率和效果临界。2)theLanguageIsconTinuellyUped,withc 20introducingFeaturesFeaturesLikeTuresLikeSlikeModeLeslikeMeSandIntIneStoImproutiMimproutimprouteverusabilityandperformance.3)

C在现代世界中:应用和行业C在现代世界中:应用和行业Apr 23, 2025 am 12:10 AM

C 在现代世界中的应用广泛且重要。1)在游戏开发中,C 因其高性能和多态性被广泛使用,如UnrealEngine和Unity。2)在金融交易系统中,C 的低延迟和高吞吐量使其成为首选,适用于高频交易和实时数据分析。

C XML库:比较和对比选项C XML库:比较和对比选项Apr 22, 2025 am 12:05 AM

C 中有四种常用的XML库:TinyXML-2、PugiXML、Xerces-C 和RapidXML。1.TinyXML-2适合资源有限的环境,轻量但功能有限。2.PugiXML快速且支持XPath查询,适用于复杂XML结构。3.Xerces-C 功能强大,支持DOM和SAX解析,适用于复杂处理。4.RapidXML专注于性能,解析速度极快,但不支持XPath查询。

C和XML:探索关系和支持C和XML:探索关系和支持Apr 21, 2025 am 12:02 AM

C 通过第三方库(如TinyXML、Pugixml、Xerces-C )与XML交互。1)使用库解析XML文件,将其转换为C 可处理的数据结构。2)生成XML时,将C 数据结构转换为XML格式。3)在实际应用中,XML常用于配置文件和数据交换,提升开发效率。

C#vs. C:了解关键差异和相似之处C#vs. C:了解关键差异和相似之处Apr 20, 2025 am 12:03 AM

C#和C 的主要区别在于语法、性能和应用场景。1)C#语法更简洁,支持垃圾回收,适用于.NET框架开发。2)C 性能更高,需手动管理内存,常用于系统编程和游戏开发。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

将Eclipse与SAP NetWeaver应用服务器集成。

VSCode Windows 64位 下载

VSCode Windows 64位 下载

微软推出的免费、功能强大的一款IDE编辑器

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

功能强大的PHP集成开发环境

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用