CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

    • 双指针法理论基础
    • 左右指针

      • 验证回文串
      • 最多删除一个字符得到回文
      • 回文子字符串的个数
      • 反转字符串
      • 反转字符串II
      • 两数之和 II - 输入有序数组
      • 反转字符串中的单词 III
      • 翻转字符串里的单词
      • 剑指 Offer 58 - II. 左旋转字符串
      • 有序数组的平方
      • 三数之和
      • 四数之和
      • 删除排序链表中的重复元素
      • 删除排序链表中的重复元素 II
      • 删除有序数组中的重复项
      • 压缩字符串
      • 移除元素
      • 移动零
      • 调整数组顺序使奇数位于偶数前面
        • 📃 题目描述
        • 🔔 解题思路
          • 双指针(不稳定)
          • 冒泡(稳定)
      • 最短无序连续子数组
      • 找到 K 个最接近的元素
      • 盛最多水的容器
    • 滑动窗口

    • 快慢指针

    • 其他

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 双指针法
  • 左右指针
小牛肉
2022-09-14
目录

调整数组顺序使奇数位于偶数前面

# 📃 题目描述

题目链接:剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 (opens new window)

# 🔔 解题思路

# 双指针(不稳定)

和 283. 移动零 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 一样,left 指针指向偶数,right 用来找奇数,然后将两个指针指向的元素进行交换就可以,这种方法没法保证原始顺序,是一种不稳定的算法

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0;
        int right = left + 1;
        while (left < nums.length) {
            // 当前数是偶数,向后找到第一个奇数与其交换
            if (nums[left] % 2 == 0) {
                right = left + 1;
                for (; right < nums.length; right ++) {
                    if (nums[right] % 2 != 0) {
                        swap(nums, left, right);
                        break;
                    }
                }
            }

            left ++;
        }

        return nums;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

# 冒泡(稳定)

类似于冒泡排序的思想,从后往前两两比较,如果发现偶数在前而奇数在后,则进行交换,就是相当于把奇数不断的冒泡到数组的前面

稳定的算法,但是时间复杂度 O(N^2),LC 上这道题会超时

秋招做天翼云笔试的时候有这个原题,要求保证相对顺序,这样做能 AC

class Solution {
    public int[] exchange(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i ++) {
            for (int j = n - 1; j > 0; j --) {
                int pre = nums[j - 1];
                int post = nums[j];
                // 偶数在前,奇数在后,则进行交换
                if (pre % 2 == 0 && post % 2 != 0) {
                    swap(nums, j - 1, j);
                }
            }
        }

        return nums;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
移动零
最短无序连续子数组

← 移动零 最短无序连续子数组→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式