讲师中心 微信公众号

工具推荐

视频效率加速
剧云
剧云

中文短剧剧本制作平台

updream

一键生成高质量推广成片

Laper
Laper

剧本策划到成片协作

立刻MV
立刻MV

低成本歌曲 MV、视频生成

在C++中,使用O(1)额外空间重新排列数组,使正负项交替出现

梦枫吖_4786

梦枫吖_4786

发布时间:2023-09-02 16:49:10

|

1243人浏览过

|

来源于tutorialspoint

转载

在c++中,使用o(1)额外空间重新排列数组,使正负项交替出现

我们得到一个包含正数和负数的整数类型数组,比方说,任意给定大小的 arr[] 。任务是重新排列一个数组,使得正数被负数包围。如果有更多的积极和 负数将被排列在数组的末尾。

让我们看看不同的输入输出情况 −

输入 − int arr[] = {-1, -2, -3, 1, 2, 3}

输出 − 排列前的数组:-1 -2 -3 1 2 3 重新排列一个数组,使正负项交替出现,并且不需要额外的空间是:-1 1 -2 2 -3 3。

解释:给定一个大小为6的整数数组,其中包含正负元素。现在,我们将重新排列数组,使所有正元素都出现在负元素之前,且不需要额外的空间 被负元素和所有额外元素所包围,最终数组的末尾将添加-1 1 -2 2 -3 3,即为最终结果。

输入 - int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};

输出 - 排列前的数组:-1 -2 -3 1 2 3 5 5 -5 3 1 1 将数组按交替正负项重新排列,不使用额外空间的时间复杂度为O(1):-1 1 -2 2 -3 3 -5 5 5 3 1 1

解释 - 我们给出一个大小为12的整数数组,包含正负元素。现在,我们将按照这样的方式重新排列数组,使得所有正元素被负元素包围,并将所有额外的元素添加到数组的末尾,即-1 1 -2 2 -3 3 -5 5 5 3 1 1将是最终结果。

下面程序中使用的方法如下

  • 输入一个整数类型的数组并计算数组的大小。

    立即学习“C++免费学习笔记(深入)”;

  • 使用FOR循环打印执行重新排列操作之前的数组。

  • 通过传递数组和数组大小作为参数调用函数Rearrangement(arr, size)。

  • 在函数Rearrangement(arr, size)内部

    • 声明一个整数变量'ptr'并将其初始化为-1。

    • 从i到0的循环,直到i小于size。在循环内部,检查如果ptr大于0,然后检查如果arr[i]大于0且arr[ptr]小于0或arr[i]小于0且arr[ptr]大于0,则调用函数move_array(arr, size, ptr, i),并检查如果i - ptr大于2,则将ptr设置为ptr + 2。否则,将ptr设置为-1。

    • 检查如果ptr等于-1,则检查arr[i]大于0且!(i & 0x01)或(arr[i]小于0)且(i & 0x01),然后将ptr设置为i。

  • 在函数move_array(int arr[], int size, int ptr, int temp)内部

    • 声明一个名为'ch'的字符类型变量,并将其设置为arr[temp]。

    • 从i到temp的循环,直到i大于ptr。在循环内部,将arr[i]设置为arr[i - 1]。

    • 将arr[ptr]设置为ch。

示例

#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
   char ch = arr[temp];
   for(int i = temp; i > ptr; i--){
      arr[i] = arr[i - 1];
   }
   arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
   int ptr = -1;
   for(int i = 0; i < size; i++){
      if (ptr >= 0){
         if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
            move_array(arr, size, ptr, i);
            if(i - ptr >= 2){
               ptr = ptr + 2;
            }
            else{
               ptr = -1;
            }
         }
      }
      if(ptr == -1){
         if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
            ptr = i;
         }
      }
   }
}
int main(){
   //input an array
   int arr[] = {-1, -2, -3, 1, 2, 3};
   int size = sizeof(arr) / sizeof(arr[0]);
   //print the original Array
   cout<<"Array before Arrangement: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

输出

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

Array before Arrangement: -1 -2 -3 1 2 3
Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3

相关文章

c++速学教程(入门到精通)
c++速学教程(入门到精通)

c++怎么学习?c++怎么入门?c++在哪学?c++怎么学才快?不用担心,这里为大家提供了c++速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门AI工具

更多
豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

切问学术

切问学术是一款AI论文写作工具,复旦大学NLP团队推出的AI学术智能体。

火山引擎

火山引擎是一款面向企业的云计算与AI服务平台。

蛙蛙写作

一款AI论文写作工具,主要用于超级AI智能写作助手,适合需要提升相关任务效率的用户。

Flowith
Flowith Hot

Flowith是一款基于画布和智能体工作流的 AI 协作工作空间。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

超级简历WonderCV

一款AI办公效率工具,主要用于免费求职简历模版下载制作,应届生职场人必备简历制作神器,适合需要提升相关任务效率的用户。

音述AI
音述AI Hot

一款AI音频处理工具,主要用于音述AI是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区,适合需要提升相关任务效率的用户。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

相关专题

更多
string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

7639

2023.08.02

int占多少字节
int占多少字节

int占4个字节,意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值,在某些情况下也可能是2个字节或8个字节,int是一种常用的数据类型,用于表示整数,需要根据具体情况选择合适的数据类型,以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

3625

2024.08.29

c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

4768

2025.08.29

C++中int的含义
C++中int的含义

本专题整合了C++中int相关内容,阅读专题下面的文章了解更多详细内容。

3185

2025.08.29

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

140

2026.11.12

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

100

2026.11.12

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

60

2026.11.12

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

160

2026.11.06

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

140

2026.11.06

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C++ Reference
C++ Reference

共0课时 | 0人学习

RabbitMQ 教程手册
RabbitMQ 教程手册

共0课时 | 0人学习

C# 教程
C# 教程

共94课时 | 22.9万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn