专栏首页csico力扣 - 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

力扣 - 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

力扣 - 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题目#

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

思路1#

  • 使用头尾双指针leftright,分别指向最左边和最右边
  • left向右移动,直到遇到了偶数停下
  • right向左移动,直到遇到了奇数停下
  • 交换left和right的值
  • 如果left大于等于right,说明调整完成

代码#

class Solution {
    public int[] exchange(int[] nums) {
        int length = nums.length;
        int left = 0;
        int right = length-1;

        while (left < right) {
            // 找偶书
            while (left < right && nums[left] % 2 == 1) {
                left++;
            }
            // 找奇数
            while (right > left && nums[right] % 2 == 0) {
                right--;
            }
            // 只有在left小于right情况下才交换
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                // 交换完成后顺便指针移动一下
                left++;
                right--;
            }
        }

        return nums;
    }
}

复杂度分析#

  • 时间复杂度:O(N)O(N)
  • 空间复杂度:O(1)O(1)

思路2#

  • 使用快慢指针
  • 初始时候,两个指针都是指向最左端
  • 快指针每次前进一格,如果遇到了奇数,就喝慢指针进行交换,然后两个指针都前进一步
  • 如果两个指针在同一个位置则不进行交换

代码#

class Solution {
    public int[] exchange(int[] nums) {
        int length = nums.length;
        int slow = 0;
        int fast = 0;

        while (slow < length && fast < length) {
            if (nums[fast] % 2 == 1) {
                if (fast != slow) {
                    int temp = nums[fast];
                    nums[fast] = nums[slow];
                    nums[slow] = temp;
                }
                slow++;
            }
            fast++;
        }
        return nums;
    }
}

复杂度分析#

  • 时间复杂度:O(N)O(N)
  • 空间复杂度:O(1)O(1)

原文链接:https://www.cnblogs.com/linzeliang1222/p/15422363.html

我来说两句

0 条评论
登录 后参与评论

推荐阅读

  • TransactionalEventListener使用场景与原理分析

    开发中有这样一个场景,客服业务需要接入在线能力,基于其他团队的IM底层能力构建业务层能力,也就是需要先调二方restful服务创建群聊,然后调用本地服务创建会话,并且创建会话依赖于二方服务返回的群聊信息,那么就会出现本地服务异常回滚,但是二方服务已经调用成功的情况,如果不做处理那么下次再尝试创建群聊,用户id已经存在,创建不成功,考虑到异构服务(二方服务可能是java、C++或者其他)或者异构数据(mysql、TiDB等), 分布式事务并不是一个很好的选择,这个时候我们就可以考虑在产生异常时候手动回滚二方服务的方式。

    叔牙
    电商JavaMySQL
  • Go modules基础精进,六大核心概念全解析(上)

    上一篇文章中,笔者介绍了如何以经典的 hello world 为例创建一个 Go module 模块,需要说明的是一个模块中是可以包含多个包(package)的,它们是可以被一起发布、打包、版本化的。同时,Go Modules 也可以通过版本管理系统(github、gitlab)或者 goproxy 代理进行下载。在使用 Go Modules 之前,建议大家弄清楚息息相关的六大核心概念,以方便大家在后期的开发、使用过程中理解更加深入。

    腾讯云荐官
    Go云荐大咖
  • 如何通过本地Navicat等图形化工具连接云数据库MySQL

    开启后记得在安全组中放通对应的公网端口和3306端口(因为内部映射还是用的3306端口),不然连接可能会受阻。

    刘晓轶
    云数据库 MySQL
  • 诡异的JVM堆外内存泄漏

    ● 报警详情: MEM usage above 90% (current value: 0.9731329333728482) ● 堆外metaspace内存占用高达3GB多 ● 机器内存耗尽,宕机

    叔牙
    电商Java
  • YGC导致CPU负载过高的排查与解决

    在报警群里看到 XXX 服务所在的服务器负载很高, 4 核 16G 的配置,CPU 使用率 >90%

    叔牙
    Java电商
  • 作业帮上万个 CronJob 和在线业务混部,如何解决弱隔离问题并进一步提升资源利用率?

    吕亚霖,作业帮基础架构 - 架构研发团队负责人。负责技术中台和基础架构工作。在作业帮期间主导了云原生架构演进、推动实施容器化改造、服务治理、GO 微服务框架、DevOps 的落地实践。 别路,作业帮基础架构-高级研发工程师,在作业帮期间,负责多云 K8s 集群建设、K8s 组件研发、Linux 内核优化调优相关工作。 背景 作业帮在云原生容器化改造的过程中,随着集群规模越来越大、业务混合部署的场景越来越复杂,面临的集群问题也越来越多,走到了 Kubernetes 及容器化的深水区, 尤其是在上万个 Cr

    腾讯云原生
  • 它们的出现是必然。一文读懂零信任和SASE

    这篇我们聊聊零信任和SASE相关的概念。二哥主要介(科)绍(普)零信任这个概念的出现为什么是一种必然,当它已然出现后,从企业安全角度来看,为什么又直接催生了SASE的诞生。文章不涉及枯燥的代码和抽象的算法,大家当逛知乎一样看看吧。

    LanceZhang
  • 一个Flutter WebView侧滑bug的解决方案

    iOS版本的侧滑返回不生效,只能在页面内侧滑返回二级web页面,不能Pop整个WebView.

    晨之阴影
    FlutterWebView
  • Flutter插件式解耦架构在播放器领域中的应用

    播放器作为应用内使用最频繁的SDK之一,尝尝需要应对多种应用场景,因此如何通过合理设计框架,从而根据各个团队的需求开发出针对性的业务插件,是播放器SDK应用使用多种实用场景的重要思路。

    晨之阴影
    Flutter
  • Redis、Zookeeper实现分布式锁——原理与实践

    Redis与分布式锁的问题已经是老生常谈了,本文尝试总结一些Redis、Zookeeper实现分布式锁的常用方案,并提供一些比较好的实践思路(基于Java)。不足之处,欢迎探讨。

    binecy
    Redis分布式ZooKeeper

扫码关注云+社区

领取腾讯云代金券