当前位置: 首页 > news >正文

顺序表排序相关算法题|负数移到正数前面|奇数移到偶数前面|小于x的数移到大于x的数前面|快排思想(C)

负数移到正数前面

已知顺序表 ( a 1 , … , a n ) (a_{1},\dots,a_{n}) (a1,,an),每个元素都是整数,把所有值为负数的元素移到全部正数值元素前边

算法思想

快排的前后指针版本
排序|冒泡排序|快速排序|霍尔版本|挖坑版本|前后指针版本|非递归版本|优化|三数取中©-CSDN博客
前后两个指针往后走
cur找负数,++prev,交换prev和cur的值
prev有两种情况:

  1. 在cur还没遇到正数的时候,prev紧跟着cur
  2. 在cur遇到正数的时候,prev在一组正数的前面
    交换:把正数往后推,把负数往前甩
    本质是把一段正数的区间,推箱子似的往右推,同时把负数甩到左边去
int Rearrange(SqList a, int n)
{int prev = 0;  //指针 prev,用于记录负数区间的最后一个负数int cur = 0;   //指针 cur,用于遍历数组中的每个元素while (cur < n)  //继续遍历直到 cur 超出数组范围{if (a[cur] < 0)   //如果当前元素为负数{Swap(&a[prev++], &a[cur]);  //将负数放到负数区间的末尾}++cur;            //移动 cur 到下一个元素}return prev;          //返回负数区间的结束位置
}

![[Pasted image 20241025141506.png]]

cur指向的是负数,与prev交换,prev++
![[Pasted image 20241025141633.png]]

cur++,判断下一个元素
![[Pasted image 20241025141655.png]]

为3,cur继续往下遍历
![[Pasted image 20241025141715.png]]

cur指向-4,与prev交换,prev++
![[Pasted image 20241025141813.png]]

cur++
![[Pasted image 20241025141826.png]]

指向-1,与prev交换,prev++
![[Pasted image 20241025141906.png]]

cur++
![[Pasted image 20241025141917.png]]

为6,结束循环

小于x移到大于x前面

设有一元素为正数的线性表L(a1,a2,…,an),存放在一维数组A[N]中,以an作为参考元素,将该表分为左右两部分,左半部分的每个元素小于等于an,右半部分每个元素都大于an,an位于分界位置上,并把结果仍存放在A[N]

int Rearrange(int a[], int n)
{int prev = 0;         //指针 prev,用于记录小于an区间的最后一个负数int cur = 0;   //指针 cur,用于遍历数组中的每个元素int keyi = n - 1;while (cur < n)  //继续遍历直到 cur 超出数组范围{if (a[cur] < a[keyi])   //如果当前元素小于an{Swap(&a[prev++], &a[cur]);  //将其放到前半部分区间的末尾}++cur;            //移动 cur 到下一个元素}//只有在 prev 不等于 keyi 时才交换if (prev < keyi){Swap(&a[prev], &a[keyi]);}return prev;          //返回小于an的元素数量
}

奇数移到偶数前面

已知线性表按顺序存储,且每个元素都是整数均不相同,把所有奇数移到所有偶数前边

思想同上

int Rearrange(SqList a, int n)
{int prev = 0;  //指针 prev,用于记录负数区间的最后一个负数int cur = 0;   //指针 cur,用于遍历数组中的每个元素while (cur < n)  //继续遍历直到 cur 超出数组范围{if (a[cur] % 2 != 0)   //如果当前元素为奇数{Swap(&a[prev++], &a[cur]);  //将奇数放到前半区间的末尾}++cur;            //移动 cur 到下一个元素}return prev;          //返回奇数区间的结束位置
}

相关文章:

顺序表排序相关算法题|负数移到正数前面|奇数移到偶数前面|小于x的数移到大于x的数前面|快排思想(C)

负数移到正数前面 已知顺序表 ( a 1 , … , a n ) (a_{1},\dots,a_{n}) (a1​,…,an​)&#xff0c;每个元素都是整数&#xff0c;把所有值为负数的元素移到全部正数值元素前边 算法思想 快排的前后指针版本 排序|冒泡排序|快速排序|霍尔版本|挖坑版本|前后指针版本|非递归版…...

【小白学机器学习20】单变量分析 / 0因子分析 (只分析1个变量本身的数据)

目录 1 什么是单变量分析&#xff08;就是只分析数据本身&#xff09; 1.1 不同的名字 1.2 《戏说统计》这本书里很多概念和一般的书不一样 1.3 具体来说&#xff0c;各种概率分布都属于单变量分析 2 一维的数据分析的几个层次 2.1 数据分析的层次 2.2 一维的数据为什么…...

[软件工程]—桥接(Brige)模式与伪码推导

桥接&#xff08;Brige&#xff09;模式与伪码推导 1.基本概念 1.1 动机 由于某些类型的固有的实现逻辑&#xff0c;使它们具有两个变化的维度&#xff0c;乃至多个维度的变化。如何应对这种“多维度的变化”&#xff1f;如何利用面向对象技术是的类型可以轻松的沿着两个乃至…...

TensorFlow面试整理-TensorFlow 结构与组件

TensorFlow 的结构和组件是其功能强大、灵活性高的重要原因。掌握这些结构和组件有助于更好地理解和使用 TensorFlow 构建、训练和部署模型。以下是 TensorFlow 关键的结构与组件介绍: 1. Tensor(张量) 定义:张量是 TensorFlow 中的数据载体,类似于多维数组或矩阵。张量的…...

linux下gpio模拟spi三线时序

目录 前言一、配置内容二、驱动代码实现三、总结 前言 本笔记总结linux下使用gpio模拟spi时序的方法&#xff0c;基于arm64架构的一个SOC&#xff0c;linux内核版本为linux5.10.xxx&#xff0c;以驱动三线spi(时钟线sclk&#xff0c;片选cs&#xff0c;sdata数据读和写使用同一…...

makesense导出的压缩包是空的

md ,那些教程感觉都不是人写的&#xff0c;没说要在右边选标签&#xff0c;我本来就是一个标签&#xff0c;我以为他会自动识别打标&#xff0c;结果死活导出来空包 密码要在右边选标签&#xff0c;...

Spring Boot框架下的中小企业设备维护系统

5系统详细实现 5.1 用户信息管理 中小企业设备管理系统的系统管理员可以对用户信息添加修改删除以及查询操作。具体界面的展示如图5.1所示。 图5.1 用户信息管理界面 5.2 员工信息管理 管理员可以对员工信息进行添加修改删除操作。具体界面如图5.2所示。 图5.2 员工信息界面…...

处理文件上传和进度条的显示(进度条随文件上传进度值变化)

成品效果图&#xff1a; 解决问题&#xff1a;上传文件过大时&#xff0c;等待时间过长&#xff0c;但是进度条却不会动&#xff0c;只会在上传完成之后才会显示上传完成 上传文件的upload.component.html <nz-modal [(nzVisible)]"isVisible" [nzTitle]"文…...

【套题】大沥2019年真题——第5题

05.魔术数组 题目描述 一个 N 行 N 列的二维数组&#xff0c;如果它满足如下的特性&#xff0c;则成为“魔术数组”&#xff1a; 1、从二维数组任意选出 N 个整数。 2、选出的 N 个整数都是在不同的行且在不同的列。 3、在满足上述两个条件下&#xff0c;任意选出来的 N 个整…...

上传Gitee仓库流程图

推荐一个流程图工具 登录 | ProcessOnProcessOn是一个在线协作绘图平台&#xff0c;为用户提供强大、易用的作图工具&#xff01;支持在线创作流程图、思维导图、组织结构图、网络拓扑图、BPMN、UML图、UI界面原型设计、iOS界面原型设计等。同时依托于互联网实现了人与人之间的…...

二叉树相关OJ题 — 第一弹

目录 1. 检验两棵树是否相同 ​编辑 1. 题目解析 2. 解题步骤 2.判断一棵大树中是否包含有和一棵小树具有相同结构和节点值的子树 1. 题目解析 2. 解题步骤 3. 翻转二叉树 1. 题目解析 2.解题步骤 4. 判断一颗二叉树是否是平衡二叉树 1. 题目解析 2. 解题步骤…...

【学习笔记】RFID

RFID 1、 概述 1.1、RFID 介绍 1.2、RFID 发展史 1.3、RFID 系统的构造 1.3.1、阅读器 Reader 和 天线 Antenna 1.3.3、电子标签 tag 1.4、电子标签按吐字率分类 1.5、电子标签按能量供应的方式划分 1.6、RFID 工作流程 …...

自动化部署-01-jenkins安装

文章目录 前言一、下载安装二、启动三、问题3.1 jdk版本问题3.2 端口冲突3.3 库文件加载问题3.4 系统字体配置问题 四、再次启动五、配置jenkins5.1 解锁5.2 安装插件5.3 创建管理员用户5.4 实例配置5.5 开始使用5.6 完成 总结 前言 spingcloud微服务等每次部署到服务器上&…...

AI工具大爆发,建议每个都使用收藏

2024年被誉为AI应用元年&#xff0c;这一年人们普遍意识到&#xff0c;未来占据主导地位的将是基于大模型的应用程序&#xff0c;而不仅仅是大模型本身。因此&#xff0c;在这一趋势的推动下&#xff0c;各式各样的AI应用如雨后春笋般涌现出来。 今天就聊聊这些好用的AI工具&a…...

Mybatis之参数处理

在MyBatis中&#xff0c;参数处理是非常关键的部分&#xff0c;它负责将传入的参数正确映射到SQL语句中 单个简单类型参数 简单类型对于mybatis来说都是可以自动类型识别的&#xff1a; 也就是说对于mybatis来说&#xff0c;它是可以自动推断出ps.setXxxx()方法的。ps.setSt…...

windows内核探索--打印windows的GDT表(全局描述符表)

x86 #include <windows.h> #include<stdio.h> #include "x86struct.h" void PrintSegmentDescriptor(ULONG64* sd, WORD Count); SegmentSelector GetSegmentSelector(USHORT Selector); int main() {printf("0环cs段寄存器 ");GetSegmentSel…...

【ChatGPT】让ChatGPT帮助进行头脑风暴与创意生成

让ChatGPT帮助进行头脑风暴与创意生成 在日常工作和生活中&#xff0c;创意和头脑风暴是解决问题、创新和推动项目的关键步骤。ChatGPT&#xff0c;作为一个强大的语言模型&#xff0c;不仅可以提供信息和答案&#xff0c;还可以成为强大的头脑风暴工具&#xff0c;帮助用户快…...

大数据处理随堂测试

HDFS MapReduce HBase Spark...

2024最新pycharm安装教程及基本使用(超详细,新手小白必看)

文章目录 前言一、官网下载二、安装步骤三、使用示范四、番外篇&#xff08;汉&#xff09;大纲 PythonPyCharm安装包领取方式戳‘这块里’ 前言 一、官网下载 1. 进入pycharm官网&#xff0c;点击下载 PyCharm: The Python IDE for data science and web development by J…...

三国杀钓鱼自动化

三国杀钓鱼脚本 前言 本来是想做必杀的&#xff0c;但是后来测试了大约400钓发现纯靠连点没有漏掉的鱼&#xff0c;所以必杀功能就舍弃了。 我pyinstaller打包后运行.exe居然黑屏了&#xff1f;&#xff1f;&#xff1f;可能是多进程报错处理没写好&#xff0c;反正还是用vsc…...

在pycharm中使用sqllite

在pycharm中使用sqllite sqllite 简介 SQLite 是一个开源的、轻量级的、关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;它设计用于嵌入到应用程序中&#xff0c;并且可以在无需外部服务器进程的情况下运行。SQLite 提供了完整的 SQL 语言支持&#xff0c;允…...

Linux——文件操作

前言 1&#xff09;在Linux下面&#xff0c;一切皆文件&#xff0c;文件文件内容文件属性 2&#xff09;在访问文件是&#xff0c;都得先将文件打开&#xff0c;修改文件的本质其实还是通过执行代码的形式修改。 3&#xff09;文件是被进程打开的&#xff0c;一个进程可以打…...

数据结构 ——— 数组栈oj题:有效括号

目录 题目要求 代码实现 题目要求 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串是否有效 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每…...

Character AI被起诉!14岁青少年自杀,AI陪伴何去何从

终于&#xff0c;AI在青少年心理问题方面&#xff0c;被推上了风口浪尖。 最近&#xff0c;美国佛罗里达州&#xff0c;一名14岁男孩Sewell Setzer的父母控告Character AI公司&#xff0c;声称孩子沉迷该公司的AI聊天机器人&#xff0c;最后走上了自杀的道路。 跟AI聊天还能致…...

CSS3 动画相关属性实例大全(三)(columns、filter、flex、flex-basis 、flex-grow、flex-shrink属性)

CSS3 动画相关属性实例大全&#xff08;三) &#xff08;columns、filter、flex、flex-basis 、flex-grow、flex-shrink属性&#xff09; 本文目录&#xff1a; 一、columns属性&#xff08;设置元素的列宽和列数&#xff09; 二、filter属性&#xff08;调整图像、背景和边…...

中国最厉害的思想家改名大师颜廷利:以诚信为基,塑企业信誉

跨文化融合&#xff0c;共筑包容性文化殿堂。尊重差异&#xff0c;促进团队合作&#xff0c;以诚信为基&#xff0c;塑企业信誉。融合《升命学说》智慧&#xff0c;推动员工多元化&#xff0c;践行社会责任&#xff0c;树立良好形象。创新不息&#xff0c;持续学习&#xff0c;…...

Python 代码实现用于进行水质模拟和优化加氯量

# -*- coding:utf-8 -*- import epamodule as em import epanetmsxmodule as msx import pandas as pd import numpy as np# 水质模拟,会产生一个rpt文件,但并不是返回这个文件。 def quality_simulation(inp_file,rpt_file,msx_file...

挖矿病毒来势汹汹

病毒来了, 我的个人站点使用了 wordpress, 它的不知哪个漏洞让黑客攻入了我的站点 使用 top 命令看到了有不明进程始终占据了 100% 的 CPU snapshot 1 snapshot 2 通过以下 "三板斧"可以查杀这个进程 先用 top (shiftp) 查找占据 CPU 最多的进程根据其进程号 pid 查看…...

国产数据库的蓝海在哪?

昨天有幸参加了 OceanBase2024年度发布会。在过去的几年中&#xff0c;OB 作为国内自主研发的分布式数据库&#xff0c;取得了令人瞩目的成就&#xff0c;特别是在金融行业&#xff0c;OB 通过不断的技术革新和优化&#xff0c;已经成为行业的领导者之一。OceanBase 展现了强大…...

MySQL~表的操作(创建表,查看表,修改表,删除表)

1.创建表 1.1.创建表 首先要选择需要操作的数据库&#xff0c;USE 数据库名&#xff0c;后续可以根据实际情况操作时添加。 USE fruitsales;建表语法&#xff1a; create table 表名( 字段名1 数据类型, 字段名2 数据类型, ); 实例&#xff1a;创建fruit_bak1表。 create t…...