LeetCode 0922.按奇偶排序数组 II:O(1)空间复杂度-一次遍历双指针

【LetMeFly】922.按奇偶排序数组 II:O(1)空间复杂度-一次遍历双指针

力扣题目链接:https://leetcode.cn/problems/sort-array-by-parity-ii/

给定一个非负整数数组 nums,  nums 中一半整数是 奇数 ,一半整数是 偶数

对数组进行排序,以便当 nums[i] 为奇数时,i 也是 奇数 ;当 nums[i] 为偶数时, i 也是 偶数

你可以返回 任何满足上述条件的数组作为答案

 

示例 1:

输入:nums = [4,2,5,7]
输出:[4,5,2,7]
解释:[4,7,2,5],[2,5,4,7],[2,7,4,5] 也会被接受。

示例 2:

输入:nums = [2,3]
输出:[2,3]

 

提示:

  • 2 <= nums.length <= 2 * 104
  • nums.length 是偶数
  • nums 中一半是偶数
  • 0 <= nums[i] <= 1000

 

进阶:可以不使用额外空间解决问题吗?

解题方法:双指针

使用两个指针分别指向奇数下标和偶数下标。

当偶数下标指针不越界时,如果偶数下标指针指向的是偶数,就右移到下一个偶数下标;否则如果奇数下标指针指向的是奇数,就右移到下一个奇数下标;否则(奇数指针指偶数,偶数指针指奇数)就交换二者并集体右移。

为什么“当偶数下标指针不越界”这一个条件就够了?因为偶数下标越界时,说明偶数下标的元素全部符合,也说明奇数下标的元素全部合规了。

  • 时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))
  • 空间复杂度 O ( 1 ) O(1) O(1)

AC代码

C++
/** @Author: LetMeFly* @Date: 2025-02-04 22:15:09* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-04 22:23:51*/
class Solution {
public:vector<int> sortArrayByParityII(vector<int>& nums) {for (int i = 0, j = 1; i < nums.size();) {if (nums[i] % 2 == 0) {i += 2;} else if (nums[j] % 2) {j += 2;} else {swap(nums[i], nums[j]);i += 2;j += 2;}}return nums;}
};
Python
'''
Author: LetMeFly
Date: 2025-02-04 22:25:05
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-04 22:26:17
'''
from typing import Listclass Solution:def sortArrayByParityII(self, nums: List[int]) -> List[int]:i, j = 0, 1while i < len(nums):if nums[i] % 2 == 0:i += 2elif nums[j] % 2:j += 2else:nums[i], nums[j] = nums[j], nums[i]i += 2j += 2return nums
Java
/** @Author: LetMeFly* @Date: 2025-02-04 22:25:10* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-04 22:28:26*/
class Solution {public int[] sortArrayByParityII(int[] nums) {for (int i = 0, j = 1; i < nums.length;) {if (nums[i] % 2 == 0) {i += 2;} else if (nums[j] % 2 != 0) {j += 2;} else {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;i += 2;j += 2;}}return nums;}
}
Go
/** @Author: LetMeFly* @Date: 2025-02-04 22:25:07* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-04 22:32:30*/
package mainfunc sortArrayByParityII(nums []int) []int {for i, j := 0, 1; i < len(nums); {if nums[i] % 2 == 0 {i += 2} else if nums[j] % 2 == 1 {j += 2} else {nums[i], nums[j] = nums[j], nums[i]i += 2j += 2}}return nums
}

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:https://letmefly.blog.csdn.net/article/details/145445952

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/12600.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python爬虫:1药城店铺爬虫(完整代码)

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ &#x1f434;作者&#xff1a;秋无之地 &#x1f434;简介&#xff1a;CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作&#xff0c;主要擅长领域有&#xff1a;爬虫、后端、大数据…

【蓝桥杯】日志统计

日志统计&#xff08;编程题&#xff09;https://dashoj.com/d/lqbproblem/p/53https://dashoj.com/d/lqbproblem/p/53https://dashoj.com/d/lqbproblem/p/53 题目 日志统计(编程题) 讲解 这个讲解感觉比较通俗易懂。 蓝桥杯2018年省赛B组08&#xff08;c/c&#xff09;日…

一文讲解Spring中应用的设计模式

我们都知道Spring 框架中用了蛮多设计模式的&#xff1a; 工厂模式呢&#xff0c;就是用来创建对象的&#xff0c;把对象的创建和使用分开&#xff0c;这样代码更灵活。代理模式呢&#xff0c;是用一个代理对象来控制对真实对象的访问&#xff0c;可以在访问前后做一些处理。单…

AI 算力瓶颈,硬件、算法、共享能否破局?

随着AI技术的蓬勃发展&#xff0c;它已经实现了从实验室走向千行百业&#xff0c;然而在它想要继续深入地探索各行各业&#xff0c;解锁更多应用场景时&#xff0c;算力却成为了它面前的一道关卡。 这道关卡由无数需要处理的数据和计算任务堆积而成&#xff0c;想要实现AI技术…

华为小米vivo向上,苹果荣耀OPPO向下

日前&#xff0c;Counterpoint发布的手机销量月度报告显示&#xff0c;中国智能手机销量在2024年第四季度同比下降3.2%&#xff0c;成为2024年唯一出现同比下滑的季度。而对于各大智能手机品牌来说&#xff0c;他们的市场份额和格局也在悄然发生变化。 华为逆势向上 在2024年第…

github下载失败网页打开失败 若你已经知道github地址如何cmd下载

直接打开命令行&#xff1a; winr cmd 输入&#xff1a;git clone 地址 eg&#xff1a;git clone https://github.com/akospasztor/stm32f103-dfu-bootloader

K8S学习笔记-------1.安装部署K8S集群环境

1.修改为root权限 #sudo su 2.修改主机名 #hostnamectl set-hostname k8s-master01 3.查看网络地址 sudo nano /etc/netplan/01-netcfg.yaml4.使网络配置修改生效 sudo netplan apply5.修改UUID&#xff08;某些虚拟机系统&#xff0c;需要设置才能生成UUID&#xff09;#…

二维数组 C++ 蓝桥杯

1.稀疏矩阵 #include<iostream> using namespace std;const int N 1e4 10; int a[N][N];int main() {int n, m; cin >> n >> m;for (int i 1; i < n; i) {for (int j 1; j < m; j) {cin >> a[i][j];}}for (int j m; j > 1; j--) {for (i…

macos系统jmap执行异常

jdk8环境下执行jmap异常 网上说mac环境jdk8不支持Jmap&#xff0c;需要替换成更高的jdk版本&#xff0c;更改zshrc文件的jdk版本 环境变量生效 执行jmap不再报错

Linux 传输层协议 UDP 和 TCP

UDP 协议 UDP 协议端格式 16 位 UDP 长度, 表示整个数据报(UDP 首部UDP 数据)的最大长度如果校验和出错, 就会直接丢弃 UDP 的特点 UDP 传输的过程类似于寄信 . 无连接: 知道对端的 IP 和端口号就直接进行传输, 不需要建立连接不可靠: 没有确认机制, 没有重传机制; 如果因…

HTB:UnderPass[WriteUP]

目录 连接至HTB服务器并启动靶机 信息收集 使用rustscan对靶机TCP端口进行开放扫描 使用nmap对靶机TCP开放端口进行脚本、服务扫描 使用nmap对靶机TCP开放端口进行漏洞、系统扫描 使用nmap对靶机常用UDP端口进行开放扫描 使用nmap对靶机UDP开放端口进行脚本、服务扫描 …

ARM内核:嵌入式时代的核心引擎

引言 在当今智能设备无处不在的时代&#xff0c;ARM&#xff08;Advanced RISC Machines&#xff09;处理器凭借其高性能、低功耗的特性&#xff0c;成为智能手机、物联网设备、汽车电子等领域的核心引擎。作为精简指令集&#xff08;RISC&#xff09;的典范&#xff0c;ARM核…

基于RK3588/RK3576+MCU STM32+AI的储能电站电池簇管理系统设计与实现

伴随近年来新型储能技术的高质量规模化发展&#xff0c;储能电站作为新能源领域的重要载体&#xff0c; 旨在配合逐步迈进智能电网时代&#xff0c;满足电力系统能源结构与分布的创新升级&#xff0c;给予相应规模 电池管理系统的设计与实现以新的挑战。同时&#xff0c;电子系…

【HarmonyOS之旅】基于ArkTS开发(二) -> UI开发三

目录 1 -> 绘制图形 1.1 -> 绘制基本几何图形 1.2 -> 绘制自定义几何图形 2 -> 添加动画效果 2.1 -> animateTo实现闪屏动画 2.2 -> 页面转场动画 3 -> 常见组件说明 1 -> 绘制图形 绘制能力主要是通过框架提供的绘制组件来支撑&#xff0c;支…

【算法】经典博弈论问题——威佐夫博弈 python

目录 威佐夫博弈(Wythoff Game)【模板】 威佐夫博弈(Wythoff Game) 有两堆石子&#xff0c;数量任意&#xff0c;可以不同&#xff0c;游戏开始由两个人轮流取石子 游戏规定&#xff0c;每次有两种不同的取法 1)在任意的一堆中取走任意多的石子 2)可以在两堆中同时取走相同数量…

通过Redisson构建延时队列并实现注解式消费

目录 一、序言二、延迟队列实现1、Redisson延时消息监听注解和消息体2、Redisson延时消息发布器3、Redisson延时消息监听处理器 三、测试用例四、结语 一、序言 两个月前接了一个4万的私活&#xff0c;做一个线上商城小程序&#xff0c;在交易过程中不可避免的一个问题就是用户…

第一个Qt开发实例(一个Push Button按钮和两个Label)【包括如何在QtCreator中创建新工程、代码详解、编译、环境变量配置、测试程序运行等】

目录 Qt开发环境QtCreator的安装、配置在QtCreator中创建新工程在Forms→mainwindow.ui中拖曳出我们要的图形按钮查看拖曳出按钮后的代码为pushButton这个图形添加回调函数编译工程关闭开发板上QT的GUI(选做)禁止LCD黑屏(选做)设置Qt运行的环境变量运行Qt程序如何让程序在系统启…

Spring Security(maven项目) 3.0.3.0版本

前言&#xff1a; 通过实践而发现真理&#xff0c;又通过实践而证实真理和发展真理。从感性认识而能动地发展到理性认识&#xff0c;又从理性认识而能动地指导革命实践&#xff0c;改造主观世界和客观世界。实践、认识、再实践、再认识&#xff0c;这种形式&#xff0c;循环往…

携程Java开发面试题及参考答案 (200道-上)

说说四层模型、七层模型。 七层模型(OSI 参考模型) 七层模型,即 OSI(Open System Interconnection)参考模型,是一种概念模型,用于描述网络通信的架构。它将计算机网络从下到上分为七层,各层的功能和作用如下: 物理层:物理层是计算机网络的最底层,主要负责传输比特流…

【Rust自学】16.4. 通过Send和Sync trait来扩展并发

喜欢的话别忘了点赞、收藏加关注哦&#xff0c;对接下来的教程有兴趣的可以关注专栏。谢谢喵&#xff01;(&#xff65;ω&#xff65;) 16.4.1. Send和Sync trait Rust语言本身的并发特性较少&#xff0c;目前所提及的并发特性都来自于标准库&#xff0c;而不是语言本身。其…