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

题目描述

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

思路

思路一:

首先统计奇数的个数,然后拷贝一个数组,设置两个指针,奇数指针从0开始,偶数指针从奇数个数的末尾开始遍历,填充到原数组

时间复杂度\(O(n)\) 空间复杂度\(O(n)\)

思路二:

由于要保证稳定即证奇数和奇数,偶数和偶数之间的相对位置不变,使用插入排序思想

时间复杂度\(O(n^2)\) 空间复杂度\(O(1)\)

代码实现

package Array;

/**
 * 调整数组顺序使奇数位于偶数前面
 * 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
 */
public class Solution48 {
    public static void main(String[] args) {
        Solution48 solution48 = new Solution48();
        int[] array = {1, 2, 3, 4, 5, 6};
        solution48.reOrderArray_2(array);
        for (int i :
                array) {
            System.out.print(i + " ");
        }
    }

    /**
     * 由于要保证稳定即证奇数和奇数,偶数和偶数之间的相对位置不变,使用插入排序思想
     * 复杂度:O(N2) + O(1)
     *
     * @param array
     */
    public void reOrderArray_2(int[] array) {
        if (array.length == 0 || array == null)
            return;
        int n = array.length;
        for (int i = 0; i < n; i++) {
            if (array[i] % 2 == 0) {
                int nextOddIdx = i + 1;
                while (nextOddIdx < n && array[nextOddIdx] % 2 == 0) {
                    nextOddIdx++;
                }
                if (nextOddIdx == n) {
                    break;
                }
                int nextOddVal = array[nextOddIdx];
                for (int j = nextOddIdx; j > i; j--) {
                    array[j] = array[j - 1];
                }
                array[i] = nextOddVal;
            }
        }
    }

    /**
     * 新建一个数组
     * 复杂度:O(N) + O(N)
     *
     * @param array
     */
    public void reOrderArray(int[] array) {
        int oddCnt = 0;
        for (int val : array) {
            if (val % 2 == 1) {
                oddCnt++;
            }
        }
        int[] copy = array.clone();
        int i = 0, j = oddCnt;
        for (int num : copy) {
            if (num % 2 == 1) {
                array[i++] = num;
            } else {
                array[j++] = num;
            }
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端吧啦吧啦

数据结构(二)之算法基础

3827
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day03-代码题

Java基础-day03-代码题 ★ 1生成Random随机数,范围在99-999之间 ★ ? 实现代码 package StudyJavaSE; //1.导包...

3946
来自专栏Leetcode名企之路

【Leetcode】81. 搜索旋转排序数组 II

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

1662
来自专栏Python中文社区

NumPy二元运算的broadcasting机制

NumPy中有一个非常方便的特性:broadcasting。当我们对两个不同长度的numpy数组作二元计算(如相加,相乘)的时候,broadcasting就在背...

3538
来自专栏菜鸟程序员

【Java】随机数详解

1904
来自专栏bboysoul

1493: C语言实验题――圆柱体计算

描述:已知圆柱体的底面半径r和高h,计算圆柱体底面周长和面积、圆柱体侧面积以及圆柱体体积。 输入:输入数据有一行,包括2个正实数r和h,以空格分隔。 输出:...

791
来自专栏算法channel

Leetcode|Find K Closest Elements

01 — 题目 Given a sorted array, two integers k and x, find the k closest elements ...

3694
来自专栏数据结构与算法

P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

4137
来自专栏ACM算法日常

递归算法复杂度Ω分析-分享

1. 深入认识递归 (1) 递归执行过程 例子:求N!。 这是一个简单的"累乘"问题,用递归算法也能解决。 n! ...

721
来自专栏前端儿

三角形面积

输入每行是一组测试数据,有6个整数x1,y1,x2,y2,x3,y3分别表示三个点的横纵坐标。(坐标值都在0到10000之间) 输入0 0 0 0 0 0表示输...

1442

扫码关注云+社区

领取腾讯云代金券