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

梦枫吖_4786

梦枫吖_4786

2023-09-02

1243人浏览

转载

在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将是最终结果。

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

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

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

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

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

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

      一览运营宝
      一览运营宝

      一款面向视频内容运营的AI创作工具,可辅助进行视频内容策划、创作和运营工作,帮助内容团队提高视频生产效率。

      下载
    • 从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 = 0){
         if(((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] <h2>输出</h2>
<p>如果我们运行上面的代码,它将生成以下输出</p>
<pre class="brush:php;toolbar:false;">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++在哪学?c++怎么学才快?不用担心,这里为大家提供了c++速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

c语言

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

相关专题

更多
string转int
string转int

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

2023.08.02

7639

3

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

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

2024.08.29

3625

6

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

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

2025.08.29

4768

10

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

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

2025.08.29

3185

10

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

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

2026.11.12

140

15

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

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

2026.11.12

100

15

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

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

2026.11.12

60

15

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

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

2026.11.06

160

12

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

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

2026.11.06

140

13

热门下载

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

精品课程

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

共0课时 | 0人学习

C# 教程
C# 教程

共94课时 | 22.9万人学习

C 教程
C 教程

共75课时 | 10.1万人学习