调整数组顺序使奇数位于偶数前面(剑指offer 21)Java双指针

简介: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。

一、题目描述



输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。


示例:

输入:nums = [1,2,3,4]

输出:[1,3,2,4]

注:[3,1,2,4] 也是正确的答案之一。


提示:

0 <= nums.length <= 50000

0 <= nums[i] <= 10000


二、思路讲解



借用快速排序的思想,用两个指针分别从头尾出发,左指针如果碰见奇数就继续往右,右指针如果碰见偶数就一直往左。当左指针碰到偶数、右指针碰到奇数时,交换两个指针的数,继续往中间寻找,知道两指针交汇。


三、Java代码实现



class Solution {
    public int[] exchange(int[] nums) {
        int i=0;
        int j=nums.length-1;
        while(i < j){
            //左指针找偶数,找到就跳出
            while(i<j && nums[i]%2!=0){
                i++;
            }
            //右指针找奇数,找到就跳出
            while(i<j && nums[j]%2==0){
                j--;
            }
            //交换两个指针的数
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;               
        }
        return nums;
    }
}


四、时空复杂度分析



时间复杂度        O(N)        

空间复杂度        O(1)


五、另一种双指针(效率较低)



class Solution {
    public int[] exchange(int[] nums) {
        int len = nums.length;
        if (len==0 || len==1){
            return nums;
        }
        int i = 0;
        int j = 1;
        while(i<len && j<len) {
            if(nums[i]%2 != 0){ //左指针为奇数
                i++;
                j++;
            } else {    //左指针为偶数
                if(nums[j]%2 != 0) { //左指针为偶数,右指针为奇数
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    i++;
                    j = i+1;
                } else {    //左指针为偶数,右指针为偶数
                    j++;
                }
            }
        }
        return nums;
    }
}



相关文章
|
3天前
|
存储 C++
C++程序数组与指针:深入理解与实践
C++程序数组与指针:深入理解与实践
11 1
|
21小时前
|
算法 C语言
通过指针引用数组
通过指针引用数组
5 1
|
1天前
|
存储 算法 Java
Java数组与for语句
Java数组与for语句
6 0
|
1天前
|
存储 Java 数据处理
Java数组
Java数组
9 1
|
2天前
|
存储 算法 安全
指针数组
指针数组
9 0
|
3天前
|
存储 搜索推荐 Java
【java】数组的定义与使用
//第二种方法:for each for(int[]tmp:array){//左边是数组的每个元素,右边是数组名
8 1
|
3天前
|
算法 C语言
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)(下)
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)
9 0
|
3天前
|
C语言
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)(中)
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)
14 0
|
3天前
|
C语言
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)(上)
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)
15 0
|
4天前
|
并行计算 Java API
Java 8中的接口默认方法和静态方法以及并行数组
【5月更文挑战第19天】Java 8引入了许多新特性,其中包括接口的默认方法和静态方法,以及并行数组的能力。这些特性增强了Java的面向对象编程模型和数组处理能力。让我们深入了解它们的概念和实践。
22 2